Background

The level order in Dancing Line always feels kind of random.

Problem Description

On this day, Umaru set a new rule for the level order in Dancing Line: suppose a certain level is the $n$-th released level, then its position $a_n$ satisfies $a_{n+1}=(\sqrt[k]{a_n-n}+2)^k+n+1$, and the first released level is always placed first, i.e., $a_1=2$.

But this clearly causes a problem: many positions will be empty levels. So Umaru added another restriction: adjust $k$ so that the $n$-th level satisfies $a_n \equiv b\pmod{m}$. Now Umaru gives $n,m,b$, and you need to find the smallest integer $k$ that satisfies the condition.

Input Format

The first line contains three numbers $n,m,b$.

Output Format

Output one number, representing the smallest $k$; if the smallest $k$ does not exist, output INF.

3 3 2

1

3 8 2

INF

Hint

For $30\%$ of the testdata, $n\le 100$, $0\le b<m\le 10000$.

For $50\%$ of the testdata, $n\le 10^{12}$, $0\le b<m\le 10000$.

For $100\%$ of the testdata, $n\le 10^{12}$, $0\le b<m\le 10^{12}$.

It is guaranteed that $n,m,b$ are all positive integers.

Translated by ChatGPT 5