\(P\) を固定します．

公式解説の考察をたどると，次のことが分かります： 答はある行列 \(A\) に対して \(A^n\) の成分の線形結合で書ける．

よって，Cayley Hamilton の定理から，\(N=n\) のときの答を \(a_n\) とすれば，\(\{a_n\}\) は c-recursive です（定数係数の線形漸化式を持ち，その長さは行列の行数でおさえられます）．

長さ \(k\) の数列の線形漸化式は，Berlekamp-Massey algorithm などによってその先頭の \(2k\) 項程度から復元でき（ https://judge.yosupo.jp/problem/find_linear_recurrence ），\(a_N\) の計算も \(O(k\log k\log N)\) 時間で行えます（ https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence ）．

よって，「行列で書ける」というところまでで考察は打ち切って，あとは行列の具体的な表示を求めることなく問題を解くことができます．本問の場合，適当な dp で十数個の \(a_n\) まで計算し，あとは上述の方法で答えを計算すればよいです．

• 解答例：https://atcoder.jp/contests/arc170/submissions/49396835