소수로 나눈 이항 계수

소수 $P$에 대해 다음 $Q$개의 질의를 순서대로 처리해 보자.

• $0\ N\ R$: $\binom NR\bmod P$를 구한다.
• $1\ N\ R$: $N^R\bmod P$를 구한다.
• $2\ N\ R$: $\binom NR\bmod P$를 구한다.

$R<0$ 또는 $R>N$이면 $\binom NR=0$으로 정의하며, $0^0=1$로 둔다.

첫 번째 줄에 두 정수 $P$, $Q$가 공백으로 구분되어 주어진다. $(2 \le P \le 2 \cdot 10^6; 1 \le Q \le 200\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 질의가 다음 형식 중 하나로 주어진다. 각 질의의 정수는 공백으로 구분되어 주어진다.

• $0\ N\ R$: 정수 $N$과 $R$이 주어진다. $(0 \le N \le 10^{18}; 0 \le R \le N+1)$
• $1\ N\ R$: 정수 $N$과 $R$이 주어진다. $(0 \le N < P; 0 \le R \le 10^{18})$
• $2\ N\ R$: 정수 $N$과 $R$이 주어진다. $(0 \le N < P; -1 \le R \le N+1)$

각 질의에서 구한 나머지를 질의가 주어진 순서대로 한 줄에 하나씩 출력한다.