Выход в синий цвет на Codeforces — большой повод для гордости, особенно если тебе десять лет. Пятиклассник Вася недавно вышел в синий цвет, и, в связи с этим, решил реализовать новый сложный алгоритм, который он прочитал на сайте e-maxx. Алгоритм называется «Обратный элемент в кольце по модулю». Суть алгоритма в том, что он позволяет находить обратный элемент в кольце по модулю.

Вася решил реализовать алгоритм и с его помощью сдать задачу на известной платформе для юных программистов — Codeforces. Задача заключалась в следующем: на вход даются два числа: $$$n$$$ и $$$M$$$ ($$$1 \le n \lt M \le 10^9 +7$$$), и нужно вывести одно такое число $$$k$$$, что $$$n \cdot k \equiv 1 (\mod M)$$$; $$$1 \le k \lt M$$$; $$$M$$$ - простое.

Благодаря прочитанной статье Вася знает, что для получения ответа достаточно возвести число $$$n$$$ в $$$M - 2$$$ степень по модулю $$$M$$$, доказательством чего он, конечно, не стал себя утруждать. Вася быстро написал код на эту задачу, но остался обескуражен — его великолепное решение получало WA6. В расстроенных чувствах он удалил код и решил навсегда уйти из спортивного программирования. Однако на следующий день ему не задали домашку и он решил все-таки восстановить свой код, чтобы найти в нем баг.

Помогите Васе восстановить его неправильное решение!