問題文


個の整数と整数が与えられます.

次の2つの条件を満たす,長さの整数列が何通りあるか求めてください.

ただし,答えは非常に大きくなる場合があるため,で割った余りを出力してください.

制約


入力


入力はすべて整数です.

出力


答えをで割った余りを,1行に出力してください.

サンプル


入力1
3 2
3 5 9
出力1
2

のとき,となり,条件を満たします.

のとき,となり,条件を満たします.

は,となり不適です.

よって,の2通りが答えです.

入力2
5 3
5 2 10 4 5
出力2
8

以外が条件を満たします.

提出


Go (1.14)