問題文


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

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

  

制約


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

入力


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





  

出力


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

  

入力例1


3 1
2 0

出力例1


2

つが条件を満たします。

入力例2


6 2
1 0
1 1

出力例2


0

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

入力例3


1000 0

出力例3


421678599

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

Submit


Go (1.14)