Problem Description

Given a prime $p$, an integer $b$, and an integer $n$, compute the smallest non-negative integer $l$ such that $b^l \equiv n \pmod p$.

Input Format

A single line contains $3$ integers, representing $p, b, n$ in order.

Output Format

A single line. If there exists an $l$ satisfying the requirement, output the smallest $l$; otherwise output no solution.

5 2 3

3

Hint

Constraints

• For all testdata, it is guaranteed that $2 \le b < p < 2^{31}$, $1 \le n < p$.

Translated by ChatGPT 5