Modified Fibonacci Sequence with Modulo

Given two integers N and M, your task is to compute the first N terms of a modified Fibonacci sequence. In this sequence, the n-th term is defined as the remainder when the n-th Fibonacci number is divided by M. The Fibonacci sequence is defined by the recurrence relation

$$F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1}+F_{n-2} \text{ for } n\ge2.$$

Thus, the output sequence is: [$$F_0 \mod M,\, F_1 \mod M,\, \ldots,\, F_{N-1} \mod M$$].

inputFormat

The input consists of a single line containing two space-separated integers N and M, where N (1 ≤ N ≤ 10⁵ or per problem scope) is the number of terms to compute and M (M ≥ 1) is the modulus.

outputFormat

Output the first N terms of the modified Fibonacci sequence in one line, separated by a single space. Each term is computed as $$F_i \mod M$$ for i from 0 to N-1.

5 3

0 1 1 2 0