Solve Linear Recurrence with Kitamasa

In the Advanced Mathematics Institute of Prime City, the Professor uses the Kitamasa method to compute the nth term of a linear recurrence in O(k^2 log n) time, where k is the order of the recurrence. This is far faster than the O(n) DP approach for large n. "The Kitamasa method represents the recurrence as a polynomial modulo the characteristic polynomial," the Professor explains. "We compute x^n mod (characteristic polynomial) using binary exponentiation, then combine with initial terms." Given a linear recurrence of order k: f(n) = c1*f(n-1) + c2*f(n-2) + ... + ck*f(n-k), with initial values f(0), f(1), ..., f(k-1), compute f(n) mod p. Constraints: 1 <= k <= 100, 0 <= n <= 10^18, 1 <= p <= 10^9 Input: 2 1 1 0 1 10 1000000007 Output: 55 Input: 2 1 1 0 1 1 1000000007 Output: 1