Prefix Permutation

長さ の順列 のうち、以下の条件を満たすものの個数を で割った余りを求めてください。

• を満たす全ての整数 について、 を で割った余りが である。

• ならば
• 入力は全て整数 　　

入力は以下の形式で標準入力から与えられます。

答えを出力してください。

3 1
2 0

2

と の つが条件を満たします。

6 2
1 0
1 1

0

ならば ですが、 とは限りません。

1000 0

421678599

で割った余りを求めることに注意してください。