Inverse#5213

Inverse

4 seconds

128 megabytes

Easy

Given a prime number $n$ . The multiplicative inverse of an integer $i (1 \leq i < n)$ i~(1 \le i < n) is defined as an integer $j$ such that $i \cdot j \equiv 1 (mod n)$ i \cdot j \equiv 1 \pmod{n}. It can be proven that for each $i$ there exists a unique inverse.

For all valid values of $i$ , find their corresponding inverses.

Input

One prime integer $n (2 \leq n \leq 1 0^{6})$ n~(2 \le n \le 10^6).

Output

Print $n - 1$ n - 1 integers. For each $i$ (in increasing order), print the multiplicative inverse of $i$ .

Examples

Example 1

Loading

i (1 \leq i < n)

i \cdot j \equiv 1 (mod n)

n (2 \leq n \leq 1 0^{6})

n - 1