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 行で出力してください。

入出力例

3 6 8

6

3 3 2

1

3 3 4

17

7 13 8

6372