Дано число \(x\). Ваша задача — найти количество положительных чисел \(n\) (\(1 \leq n \leq x\)), удовлетворяющих \(\)n \cdot a^n \equiv b \quad (\textrm{mod}\;p),\(\) где \(a, b, p\) — заданные константы.
Единственная строка содержит четыре целых числа \(a,b,p,x\) (\(2 \leq p \leq 10^6+3\), \(1 \leq a,b < p\), \(1 \leq x \leq 10^{12}\)). Гарантируется, что \(p\) — простое.
Выведите одно число: количество решений \(n\).
В первом примере \(n=2\) и \(n=8\) являются решениями.
2 3 5 8
2
4 6 7 13
1
233 233 10007 1
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач