No.64 Or Plus Max 2


時間制限:$3.5sec$ / メモリ制限:$1024MB$ / tester:square1001 kotamanegi

問題文

以下の問題があります。

  • 長さ N の数列 A = {A[1], A[2], A[3], ..., A[N]} がある。
  • 以下のような区間の個数を求めよ。
    • A[l] xor A[l+1] xor ... xor A[r] = A[l] + A[l+1] + ... + A[r]

この問題は簡単すぎるので、以下の問題を代わりに解いてください。

  • 長さ N の数列で 1 ≦ A[i] < P を満たし、前述の問題の答えが K となるような数列 A の通り数を求めよ。
  • mod 1,000,000,007 で求めること。

制約

  • $1$ ≦ $N$ ≦ $40$
  • $1$ ≦ $K$ ≦ $N * (N+1) / 2$
  • $2$ ≦ $P$ ≦ $1,024$ ($P$ は $2^n$ で表される数)

部分点

小課題 1 [100 点]

  • $N ≦ 7$ を満たす。
  • $P ≦ 8$ を満たす。

小課題 2 [120 点]

  • $N ≦ 24$ を満たす。
  • $P ≦ 8$ を満たす。

小課題 3 [560 点]

  • $N ≦ 24$ を満たす。
  • $P ≦ 256$ を満たす。

小課題 4 [220 点]

  • 追加の制約はない。

入力形式

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


N K P

出力

数列 A として考えられる通り数を 1,000,000,007 で割った余りを 1 行で出力してください。

入出力例

入力1

3 6 8
出力1

6
入力2

3 3 2
出力2

1
入力3

3 3 4
出力3

17
入力4

7 13 8
出力4

6372