問題文


項数 の正整数列 が与えられます。
整数の組 のうち、 を満たすものの個数を で割った余りを求めて下さい。

制約


入力



出力


条件を満たす の個数を で割った余りを求めて下さい。

サンプル


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

となるものは つです。

入力例2
1
2023
出力例2
0

提出


Go (1.14)