問題一覧 > 通常問題

No.916 Encounter On A Tree

レベル : / AI推定難易度 : 1475 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 112
作問者 : ningenMe / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 2827 / 自分の提出
問題文最終更新日: 2019-10-25 07:49:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 229 (順位表) の他の問題:

Problem Statement

You are given a perfect binary tree of depth $d$.
Here, a perfect binary tree is a tree in which every vertex either "is a leaf" or "has two children", and in which all leaves have the same depth.
The depth of the root is $1$, and the depth of the leaves is $d$.
Furthermore, for the vertex that has depth $i$ and is the $j$-th from the left, its position is defined as $2^{i-1}+j-1$, and the vertex at position $x$ is called vertex $x$.

Consider writing distinct numbers from $1$ to $2^d-1$, one each, on the $2^d-1$ vertices of this tree.
The following conditions must be satisfied.

  • For all $i,\ j$, if the depth of vertex $i$ is greater than the depth of vertex $j$, then the number written on vertex $i$ is greater than the number written on vertex $j$.
  • The number of edges on the path connecting the vertex on which $l$ is written and the vertex on which $r$ is written is $k$.
  •   
How many such ways of writing the numbers are there? Since the answer can be very large, output it modulo $10^9+7$.
Here, two ways of writing the numbers are considered different if there exists a vertex $i$ such that the numbers written on vertex $i$ differ.

Input

$d\ l\ r\ k$

All inputs are integers.
$2 \le d \le 20$
$1 \le l < r \le 2^d-1$
$1 \le k \le 10^5$

Output

Output the answer on one line. Print a newline at the end.

Sample

Sample 1
Input
2 1 2 1
Output
2

There are 2 ways: (vertex 1, vertex 2, vertex 3)=(1,2,3), (1,3,2).

Sample 2
Input
2 2 3 2
Output
2

Sample 3
Input
3 4 5 4
Output
32

Sample 4
Input
4 3 6 2
Output
0

Sample 5
Input
17 34 45 4
Output
8695321

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