#P18829. [Croatian CPC2018] Ploča

[Croatian CPC2018] Ploča

[Croatian CPC2018] Ploča

题目描述

在平面直角坐标系中,考虑左下角为 (−2n+1,−2n+1)(-2^n+1,-2^n+1)、右上角为 (2n−1,2n−1)(2^n-1,2^n-1) 的正方形区域。标出其中横、纵坐标均为奇数的所有整点,共有 4n4^n 个。

现在给这些点分配 11 至 4n4^n 的互不相同的编号,规则如下:第一象限内所有点的编号小于第二象限内所有点的编号,第二象限内所有点的编号小于第三象限内所有点的编号,第三象限内所有点的编号小于第四象限内所有点的编号。

在每个象限内部,以该象限中点集的水平、竖直对称轴交点作为新的原点,保持坐标轴方向不变,对其中的点递归采用相同的编号规则,直到每个部分只剩一个点。四个象限按通常约定分别为右上、左上、左下、右下。

下图给出 n=2n=2 时的编号:

n等于2时的编号

给定整数 kk,求所有位于直线 x+y=kx+y=k 上的已标记点的编号之和,对 109+710^9+7 取模。

输入格式

一行包含两个整数 n,kn,k(1≤n≤601\le n\le60)。

保证直线 x+y=kx+y=k 至少经过一个已标记点。

输出格式

输出一个整数,表示所求编号之和对 109+710^9+7 取模的结果。

样例 1

输入

1 0

输出

6

样例 2

输入

2 0

输出

44

样例 3

输入

2 6

输出

1

样例 4

输入

3 -14

输出

43