• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۴۰ مگابایت

مهدی که از کدزدن خسته شده‌است، امتحان درس مبانی برنامه‌نویسی را خراب کرده‌است. او می‌داند که استاد درس مبانی دقیقا $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 است.