RPS by Many People

人の人がじゃんけんをします。このじゃんけんには の 種類の手があります。

このじゃんけんにおける引き分けを、出た手が 種類以外のときと定義します。つまり、出た手が 種類だけのときと、 種類すべて出たときは引き分けです。

このじゃんけんをする人たちは、パターンが好きなので、全員あるパターンに沿って手を出します。 番目の人は、長さ のパターン に沿って、 回目には を出します。

回じゃんけんをしたとき、引き分けが何回あったか答えてください。

• 入力はすべて整数である

答えを 行に出力せよ。

2 10
3 2
0 1 2
0 1

4

出た手を順番に見ると、 です。このうち、手が 種類でない回は 回あります。

3 5
1 2 3
0
1 2
2 0 1

1

出た手を順番に見ると、 となります。 のときも引き分けとなることに注意してください。

10 1000000000000000000
1 2 3 4 5 6 7 8 9 10
1
2 0
2 1 2
2 0 2 1
2 2 1 1 2
1 1 0 2 1 2
1 1 0 2 2 1 1
0 2 0 1 2 0 2 2
2 1 2 0 1 1 2 1 0
0 0 0 1 0 2 1 0 2 1

928571428571428570