Dancing Line Level Position

In the game Dancing Line, a new rule has been introduced for ordering the levels. Suppose the level published as the n-th level has position \(a_n\). The positions follow the recurrence relation:

[ a_{n+1} = \Bigl( \sqrt[k]{a_n - n} + 2 \Bigr)^k + n + 1,\quad \text{with}\quad a_1 = 2. ]

It can be shown by induction that the closed form is given by:

[ a_n = (2n - 1)^k + n. ]

However, this might leave many positions unoccupied. To address this, an additional condition is imposed: adjust \(k\) so that the n-th level's position satisfies

[ a_n \equiv b \pmod{m}. ]

Given three integers \(n\), \(m\), and \(b\), find the smallest positive integer \(k\) such that

[ (2n-1)^k + n \equiv b \pmod{m}. ]

inputFormat

The input consists of three space-separated integers \(n\), \(m\), and \(b\) on a single line.

outputFormat

Output the smallest positive integer \(k\) that satisfies the condition.

sample

1 10 2

1