행렬과 피보나치 수의 합

\uD06C\uAE30\uAC00 $K \times K$\uC778 \uD589\uB82C $M$\uACFC \uC74C\uC774 \uC544\uB2CC \uC815\uC218 $N$, $a$, $d$\uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uD589\uB82C $M$\uC758 $r$\uD589 $c$\uC5F4 \uC6D0\uC18C\uB97C $M_{r,c}$\uB77C\uACE0 \uD558\uC790.

\uD589\uB82C $S$\uB97C \uB2E4\uC74C\uACFC \uAC19\uC774 \uC815\uC758\uD55C\uB2E4.

[ S = \sum_{i=0}^{N}{F_{a+i \cdot d} \cdot M^i}. ]

\uC5EC\uAE30\uC11C $M^0$\uB294 \uB2E8\uC704 \uD589\uB82C\uC774\uB2E4. \uD53C\uBCF4\uB098\uCE58 \uC218\uB294 $F_0 = 0$, $F_1 = 1$\uC774\uACE0, $i > 1$\uC77C \uB54C $F_i = F_{i-1} + F_{i-2}$\uB85C \uC815\uC758\uD55C\uB2E4.

\uD589\uB82C $S$\uB97C \uAD6C\uD558\uB77C.

\uCCAB\uC9F8 \uC904\uC5D0 $K$, $a$, $d$, $N$\uC774 \uC8FC\uC5B4\uC9C4\uB2E4.

\uB2E4\uC74C $K$\uAC1C\uC758 \uC904\uC5D0\uB294 \uD589\uB82C $M$\uC758 \uC6D0\uC18C\uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uC774 \uC911 $i$\uBC88\uC9F8 \uC904\uC5D0\uB294 $M_{i,1}$, $M_{i,2}$, ..., $M_{i,K}$\uAC00 \uACF5\uBC31\uC73C\uB85C \uAD6C\uBD84\uB418\uC5B4 \uC8FC\uC5B4\uC9C4\uB2E4.

\uCD1D $K$\uAC1C\uC758 \uC904\uC5D0 \uD589\uB82C $S$\uC758 \uC6D0\uC18C\uB97C $998244353$\uC73C\uB85C \uB098\uB208 \uB098\uBA38\uC9C0\uB97C \uCD9C\uB825\uD55C\uB2E4.

$i$\uBC88\uC9F8 \uC904\uC5D0\uB294 $S_{i,1}$, $S_{i,2}$, ..., $S_{i,K}$\uB97C \uACF5\uBC31\uC73C\uB85C \uAD6C\uBD84\uD558\uC5EC \uCD9C\uB825\uD55C\uB2E4.

• $1 \le K \le 100$
• $0 \le a, d \le 10^9$
• $0 \le N \le 10^{1000}$
• $0 \le M_{i,j} < 998244353$