题目描述

一个超对称矩阵是递归定义的方阵：

1. 任意 $1\times 1$ 矩阵都是超对称矩阵；

2. 当 $N>1$ 时，一个 $N\times N$ 矩阵是超对称矩阵，当且仅当同时满足：

   • 它关于竖直中轴、水平中轴、主对角线、副对角线都对称；

   • 位于矩阵四个角上的四个子矩阵都是超对称矩阵。每个角上的子矩阵大小为

     $$\left\lfloor \frac N2\right\rfloor \times \left\lfloor \frac N2\right\rfloor.$$

一个二进制矩阵是指所有元素均为 $0$ 或 $1$ 的矩阵。

一个 $N\times N$ 二进制超对称矩阵的值定义为：把矩阵元素按行从上到下、每行从左到右依次读出，得到一个长度为 $N^2$ 的二进制数。这个二进制数对应的整数就是该矩阵的值。

任务

给定 $N$ 和 $K$，在所有 $N\times N$ 二进制超对称矩阵的值中，按从小到大排序，求第 $K$ 小的值。

由于答案可能非常大，只需要输出答案对 $1\,000\,000\,007$ 取模后的结果。

输入格式

第一行包含一个整数 $N$。

第二行包含一个只由字符 0 和 1 组成的字符串，表示 $K$ 的二进制表示。保证第一个字符为 1。

输出格式

输出一个整数，表示第 $K$ 小的二进制超对称矩阵的值对 $1\,000\,000\,007$ 取模的结果。

数据范围

• $1\le N\le 1\,000\,000\,000$；
• $1\le K\le 2^{1\,000\,000}$；
• 保证对于给定的 $N$，至少存在 $K$ 个 $N\times N$ 二进制超对称矩阵。

子任务

样例

输入

3
100

输出

186

解释

$K=100_2=4$。

第 $4$ 小的矩阵为：

0 1 0
1 1 1
0 1 0

按行读取得到二进制数：

010111010

其十进制值为 $186$。