Вася изучает модульную арифметику. Для тренировки он сосчитал сумму $$$1^1 + 2^2 + ... + n^n$$$ по модулю $$$m$$$. Другими словами, он нашёл остаток от деления этой суммы на $$$m$$$.
У Васи получился ответ $$$r$$$. Однако, при вычислении он допустил ошибку — пропустил одно из слагаемых. Определите номер слагаемого, которое он пропустил.
Вводятся три целых числа $$$n$$$, $$$m$$$ и $$$r$$$, каждое в отдельной строке ($$$2 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$, $$$0 \le r \ \lt m$$$).
Выведите целое число от $$$1$$$ до $$$n$$$ — номер пропущенного слагаемого. Если есть несколько верных ответов, выведите наименьший из них. Если решения нет, то выведите 0.
Подзадача 1 (до 30 баллов): $$$n \le 5$$$
Подзадача 2 (до 30 баллов): $$$n \le 100$$$
Подзадача 3 (до 40 баллов): $$$n \le 10^5$$$
3108
2
3102
0
