Description

Given positive integers $n, p$, find the multiplicative inverses modulo $p$ for all integers in $[1, n]$.

The multiplicative inverse of $a$ modulo $p$ is defined as the solution $x$ to $ax\equiv1\pmod p$.

Input Format

One line with two positive integers $n, p$.

Output Format

Output $n$ lines, where the $i$-th line denotes the multiplicative inverse of $i$ modulo $p$.

10 13

1
7
9
10
8
11
2
5
3
4

Hint

All testdata satisfy $1 \leq n \leq 3 \times 10 ^ 6$, $n < p < 20000528$. The input guarantees that $p$ is prime.

Translated by ChatGPT 5