Hello Codeforcers! As a student of department of mathematics, I'd like to demonstrate an application of Extended Field.

First we should include the idea of splitting field, a splitting field F of a polynomial P is the smallest field such that

I use the word "smallest" with the sense that if P split over E implies .

In the other word, P decomposes into linear factor under it's splitting field.

For example:

1. P = x² + 1 does not split over but split over where which is widely used as complex.

2. Let p = 998244353 = 7 * 17 * 2²³ + 1, P = x²²⁴ - 1 does not split over but split over where . The multiplication order ord(w²) = 2²³.

3. Let p = 10⁹ + 7, Fibonacci number can be easily written as . Where φ, ψ are both root of (Remark that x² = 5 has no root in Z_p

The problem to be demonstrated is 718C - Sasha and Array.

In the problem, we should handle Fibonacci number 1, 1, 2, 3, 5, 8, ... with the formula

Once a splitting field implementation is done, we can FFT under module more than