#3194. 「eJOI2019」挂架

内存限制:100 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hiuseues2

题目描述

本题译自 eJOI2019 Problem B「Hanging Rack

有一棵 n 层的满二叉树,第 i 层( 0 \le i \le n-1 )有 2^i 个结点。
i 层( 1 \le i \le n-1 )的第 j 个结点( 1 \le j \le 2^i ),是第 i-1 层第 \lceil \frac{j}{2} \rceil 个结点的子结点。如 j 是奇数则是左子结点,否则是右子结点。
每个叶子结点都可以挂衣服。
对于每个非叶子结点,设它左子树和右子树上分别挂了 w_l w_r 件衣服,要求挂完每件衣服后都有 w_l-w_r \in \{0, 1\} 注意不能为 -1 )。
请求出第 k 件衣服应该挂在第几个叶子结点,输出这个编号模 10^9+7 的值。

输入格式

一行,两个正整数 n, k

输出格式

一行,一个正整数,表示所求叶子结点编号模 10^9+7 的值。

样例

样例输入 1

3 2

样例输出 1

5

样例解释 1

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

k (0,1) (1,1) (1,2) (2,1) (2,2) (2,3) (2,4)
1 1,0 1,0 0,0 1,0 0,0 0,0 0,0
2 1,1 1,0 1,0
3 2,1 1,1 1,0
4 2,2 1,1 1,0
5 3,2 2,1 1,1
6 3,3 2,1 1,1
7 4,3 2,2 1,1
8 4,4 2,2 1,1

样例输入 2

5 10

样例输出 2

19

样例解释 2

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

数据范围与提示

对于 100\% 的数据,保证 1 \le k \le \min\{2^n, 10^{18}\}

子任务编号 数据范围 分值
1 1 \le n \le 10 20
2 1 \le n \le 20 20
3 1 \le n \le 10^6 60