正整数が与えられます.行列を以下のように定めます.
の成分をと表す.
以下の問いに回答えてください.問の形式は以下の通りです.
入力は以下の形式で標準入力から与えられます.
答えを行に出力せよ.行目には問の答えを出力せよ.
4 4 2 1 2 4 1 1 3 3
2 0 1 1
です. よって です.
1000000 10 873930 407326 573419 416908 36023 290264 59455 62049 393215 235603 260609 88214 976337 630158 450140 309938 276091 634466 762854 398528
0 0 0 0 0 0 0 0 0 0