No.916 Encounter On A Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 70
作問者 : ningenMeningenMe / テスター : tempura_pptempura_pp
2 ProblemId : 2827 / 出題時の順位表

問題文

深さ$d$である完全二分木が与えられます。
ここで、完全二分木とは全ての頂点が「葉である」または「2つの子を持つ」をみたす木であり、かつ全ての葉の深さが同じであるようなものを指します。
また、根の深さを$1$とし、葉の深さを$d$とします。
さらに、深さが$i$で左から$j$番目である頂点に対して位置を$2^{i-1}+j-1$で定義し、 位置が$x$である頂点のことを頂点$x$と呼ぶことにします。

この木にある$2^d-1$個の頂点に対して$1$から$2^d-1$の異なる番号を1つずつ書き込むことを考えます。
このとき、以下の条件を満たすようにします。

  • すべての$i,\ j$について、頂点$i$の深さが頂点$j$の深さよりも大きいならば、 頂点$i$に書き込まれる番号は頂点$j$に書き込まれる番号より大きい
  • $l$が書き込まれた頂点と$r$が書き込まれた頂点を結ぶパスに含まれる辺の本数は$k$本である。
  •   
このような番号の書き込み方の総数は何通りでしょうか?答えは非常に大きくなることがあるため$10^9+7$で割った余りを答えてください。
ただし、2つの番号の書き込み方が異なるとは、ある頂点$i$が存在して頂点$i$に書き込まれた番号が異なることを言います。

入力

$d\ l\ r\ k$

入力は全て整数である
$2 \le d \le 20$
$1 \le l < r \le 2^d-1$
$1 \le k \le 10^5$

出力

答えを1行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
2 1 2 1
出力
2

(頂点1, 頂点2, 頂点3)=(1,2,3), (1,3,2)の2通りです。

サンプル2
入力
2 2 3 2
出力
2

サンプル3
入力
3 4 5 4
出力
32

サンプル4
入力
4 3 6 2
出力
0

サンプル5
入力
17 34 45 4
出力
8695321

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。