#L3196. 「eJOI2019」挂架

    ID: 5797 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>树结构递推组合数学数据结构

「eJOI2019」挂架

题目描述
本题译自 eJOI2019 Problem B. Hanging Rack

有一棵 nn 层的满二叉树,第 ii 层(0in10 \le i \le n-1)有 2i2^i 个结点。
ii 层(1in11 \le i \le n-1)的第 jj 个结点(1j2i1 \le j \le 2^i),是第 i1i-1 层第
j2\lceil \frac{j}{2} \rceil 个结点的子结点。如 jj 是奇数则是左子结点,否则是右子结点。
每个叶子结点都可以挂衣服。

对于每个非叶子结点,设它左子树和右子树上分别挂了 wlw_lwrw_r 件衣服,要求挂完每件衣服后都有 wlwr{0,1}w_l-w_r \in \{0, 1\}(注意不能为 1-1)。

请求出第 kk 件衣服应该挂在第几个叶子结点,输出这个编号模 109+710^9+7 的值。


输入格式
一行,两个正整数 n,kn, k


输出格式
一行,一个正整数,表示所求叶子结点编号模 109+710^9+7 的值。


样例 1
输入

3 2

输出

5

挂衣服的顺序是 1,5,3,7,2,6,4,81, 5, 3, 7, 2, 6, 4, 8
下面给出了挂每件衣服后各个结点的 wl,wrw_l, w_r 值((i,j)(i, j) 表示第 ii 层第 jj 个结点):


样例 2
输入

5 10

输出

19

挂衣服的顺序是 1,17,9,25,5,21,13,29,3,19,1, 17, 9, 25, 5, 21, 13, 29, 3, 19, \cdots


数据范围与提示
对于 100%100\% 的数据,保证 1kmin{2n,1018}1 \le k \le \min\{2^n, 10^{18}\}

子任务编号 数据范围 分值
1 1n101 \le n \le 10 2020
2 1n201 \le n \le 20
3 1n1061 \le n \le 10^6 6060