- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۴۰ مگابایت
مهدی که از کدزدن خسته شدهاست، امتحان درس مبانی برنامهنویسی را خراب کردهاست. او میداند که استاد درس مبانی دقیقا \(k\) نفر را میاندازد. مهدی میخواهد بداند که آیا مبانی را میافتد یا نه. برای همین میخواهد نمرهی اولین کسی که درس را میافتد (یا \(k\)امین کمترین نمره) را پیدا کند. نمرهی نفر \(i\)م به ترتیب الفبا، \(a_i\) است. چون تعداد دانشجویان زیاد است، استاد نمرهها را به این صورت رد میکند: \[ a_1 = m \] \[ a_i =(x \times a_{i-1} + y) \ mod \ p \ (2 \le i \le n) \] که \(p\) برابر است با \(10^9 + 7\).
به محدودیت حافظهی غیر معمول در این سوال دقت کنید!
ورودی
در تنها سطر ورودی به ترتیب اعداد \(n\)، \(k\)، \(m\)، \(x\)، \(y\) به شما داده شده است. \[ 1 \le k \le n \le 10\ 000\ 000 \] \[ 0 \le m, x, y < p \]
خروجی
در تنها خط خروجی نمرهی \(k\)امین کمترین نمره را بنویسید.
مثال
ورودی نمونه ۱
5 3 1 1 2
خروجی نمونه ۱
5
در این نمونه، دنبالهی نمرهها برابر 9 7 5 3 1 است و سومین کوچکترین آنها برابر ۵ میشود.
ورودی نمونه ۲
5 3 1 1000000006 0
خروجی نمونه ۲
1
در این نمونه، دنبالهی نمرهها برابر 1 1000000006 1 1000000006 1 است.