题目描述

一个挂架由 $n$ 层的连接杆组成。第 $i$ 层（$i\in [0,n-1]$）有 $2^i$ 根连接杆。第 $0$ 层的连接杆的中点被固定在墙上。在其他层，第 $j$ 个（$j\in[1,2^i]$）连接杆的中点被上一层的第 $\left\lceil{\dfrac{j}{2}}\right\rceil$ 个连接杆所固定。如果 $j$ 是奇数，那就是被上一个连接杆所的左端点固定的，如果是偶数，那就是右端点。在最底层，每一个连接杆的左右端点都有一个用来挂衣服的挂钩。一个挂钩可以挂至多一件衣服。

举个例子，当 $n=3$ 时，这个挂架长这样：

Mojca 想要把她的所有衣服挂到这个挂架上。每一件衣服恰好重一个单位。以免破坏挂架脆弱的结构，她必须按照某种特定的规则（或顺序）依次挂衣服：

• 当挂好一件衣服后，对于每一个连接杆，假设它左端点下方的总重为 $w_l$，右端点为 $w_r$，那么必须确保 $w_l-w_r \in {0,1}$。 注意，不可以为 $-1$ 。

连接杆和挂钩很轻，重量可忽略不计。

Mojca 听说你很强，所以来寻求你的帮助。给定两个整数 $n,k$ ，请确定第 $k$ 个衣服应该挂在哪个挂钩上。

输入格式

输入仅一行，两个正整数 $n,k$。

输出格式

输出包含一行，共一个整数，表示第 $k$ 个衣服应该挂的挂钩的编号，并对 $(10^9+7)$ 取模，挂钩的编号不等同于连接杆的编号。

3 2

5

5 10

19

提示

【样例输入输出解释】

样例 1 解释

• 挂钩的使用顺序应为：$1,5,3,7,2,6,4,8$，那么第二件衣服就应该挂在第 $5$ 个挂钩上。

样例 2 解释

• 这里，挂钩是使用顺序为：$1, 17,9, 25,5, 21,13,29,3,19,\text{etc.}$

---

【数据规模与约定】

本题采用多测试点捆绑测试，共有 3 个子任务。

• Subtask 1（20 points）：$n \leq 10$。
• Subtask 2（20 points）：$n \leq 20$。
• Subtask 3（60 points）：无特殊限制。

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$1 \leq k \leq \min(2^n, 10^{18})$。

---

【说明】

原题来自：eJOI2019 Problem B. Hanging Rack

翻译提供：@_Wallace_（感觉 LOJ 的翻译 被过于简化容易导致歧义，所以供题者自行翻译了一遍）