No.916 Encounter On A Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 70
作問者 : ningenMeningenMe / テスター : tempura_pptempura_pp
2 ProblemId : 2827 / 出題時の順位表
問題文最終更新日: 2019-10-25 07:49:27

問題文

深さ$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

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。