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
In the other word, P decomposes into linear factor under it's splitting field.
For example:
P = x2 + 1 does not split over
but split over 
where 
Let p = 998244353 = 7 * 17 * 223 + 1, P = x224 - 1 does not split over
but split over 
where 
. The multiplication order ord(w2) = 223
The problem to be demonstrated is 718C - Sasha and Array.
In the problem, we should handle Fibonacci number 1, 1, 2, 3, 5, 8, .... f(n) = x^2 + x + 1
Once a splitting field implementation is done, we can FFT under module more than
