All Inverses at Once

Difficulty: 1600 5000 ms 128 MB

number-theory

Given a prime P and N, print the modular inverses of 1, 2, ..., N modulo P.

Input: the first line has P; the second line has N.

Output: N integers: the inverse of each i in 1..N.

Constraints:

• 2 ≤ P ≤ 10⁹, P prime
• 1 ≤ N < P
• N ≤ 10⁶

Sample Tests

7
5

1 4 5 2 3

11
1

1

Read the Editorial