E. Уравнение конгруэнтности
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано число $$$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$$$.

Примеры
Входные данные
2 3 5 8
Выходные данные
2
Входные данные
4 6 7 13
Выходные данные
1
Входные данные
233 233 10007 1
Выходные данные
1
Примечание

В первом примере $$$n=2$$$ и $$$n=8$$$ являются решениями.