RPS by Many People

2 secs 1024 MB
magurofly

問題文


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

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

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

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

制約


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

入力


出力


答えを 行に出力せよ。

入出力例


入力例1
2 10
3 2
0 1 2
0 1
出力例1
4

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

入力例2
3 5
1 2 3
0
1 2
2 0 1
出力例2
1

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

入力例3
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
出力例3
928571428571428570

提出


Go (1.14)