- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
رتبهی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!
رتبهی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!
ما هم مثل شما نفهمیدیم این دیالوگ بالا برای چه وقتی بوده است! اما احتمالا ساختهی ذهن مریض طراح بوده و منبع موثقی ندارد! برای اینکه دیگر این مشکل پیش نیاید! میخواهیم جملههایی که شنیدهایم و به درست بودنشان اطمینان داریم را بازنویسی کنیم!!!
به این منظور جدولی \(n \times m\) تعبیه شده است. در سطر \(x\) و ستون \(y\) به اندازه ی \(\max(a + x \times b, c + y\times d)\) جمله مینویسیم. حال مجموع تعداد جملهها را از شما میخواهیم.
در واقع برای همهی ستونها یک دنبالهی حسابی با قدر نسبت \(b\) و مقدار اولیهی \(a\) و برای همهی سطرها یک دنبالهی حسابی با قدر نسبت \(d\) و مقدار اولیه \(c\) در نظر گرفتیم و در هر خانه به تعداد بیشینه این دو عدد، جمله مینویسیم. شما باید جواب را که تعداد کل کلمه هاست به پیمانهی \(10 ^ 9 +7 \) چاپ کنید.
ورودی
در تنها خط ورودی به ترتیب اعداد \(n\)، \(m\)، \(a\)، \(b\)، \(c\) و \(d\) آمدهاند.
\[1 \leq n, m \leq 1\ 000\ 000\ 000\]
\[0 \leq a,b,c,d \leq 1\ 000\ 000\]
خروجی
در تنها خط خروجی یک عدد به عنوان جواب مساله چاپ کنید.
مثال
ورودی نمونه ۱
3 3 0 1 0 2
خروجی نمونه ۱
21
توضیح نمونه اول :
جفت ها عبارتند از:
(0,0) (0,2) (0,4)
(1,0) (1,2) (1,4)
(2,0) (2,2) (2,4)
که مجموع بیشینههای هر جفت برابر با ۲۱ میشود.
ورودی نمونه ۲
75164 100 97702 84646 95867 454
خروجی نمونه ۲
997345518