결국 주기적인 수열

음이 아닌 정수 $N$ 에 대하여 함수 $f\colon {0, 1, \dots, N} \to {0, 1, \dots, N}$ 가 주어지고, $n \le N$ 인 음이 아닌 정수 $n$ 이 주어진다. 이를 이용해 다음과 같이 무한 수열 $F = f^{1}(n), f^{2}(n), \dots, f^{k}(n), \dots$ 을 만들 수 있다. 여기서 $f^{k}(n)$ 은 $f^{1}(n) = f(n)$, $f^{k+1}(n) = f(f^{k}(n))$ 으로 재귀적으로 정의된다.

이렇게 만든 수열 $F$ 는 항상 결국 주기적이다. 즉, 어느 지점 이후로는 같은 구간이 반복된다. 예를 들어 $1, 2, 7, 5, 4, 6, 5, 4, 6, 5, 4, 6, \dots$ 와 같다.

$N \le 11000000$, $n \le N$, 그리고 함수 $f$ 가 주어질 때 수열 $F$ 의 주기를 구하여라.

입력의 각 줄에는 $N$, $n$, 그리고 함수 $f$ 를 후위 표기법(역폴란드 표기법, RPN)으로 나타낸 식이 주어진다. 피연산자는 부호 없는 정수 상수, 문자 $N$, 또는 변수 $x$ 중 하나이다. 연산자는 이항 연산자만 허용되며 $+$ (덧셈), $*$ (곱셈), $%$ (나머지, 즉 정수 나눗셈의 나머지) 세 가지이다. 피연산자와 연산자는 공백으로 구분된다. $%$ 연산자는 각 함수에서 정확히 한 번만 나타나며, 항상 가장 마지막(가장 오른쪽, 즉 가장 위쪽) 연산자이고 그 두 번째 피연산자는 언제나 입력으로 주어진 $N$ 이다. 예를 들어 다음 후위 표기식

2 x * 7 + N %

은 익숙한 중위 표기 $(2 * x + 7) % N$ 에 해당한다. 모든 입력 줄의 길이는 100자 미만이다. 입력의 마지막 줄은 $N = 0$ 이며, 이 줄은 처리하지 않는다.

입력의 각 줄마다 한 줄에 정수 하나를 출력한다. 그 값은 해당 입력 줄의 데이터로 만든 수열 $F$ 의 주기이다.