#P17828. [Ontak2022]HSM

[Ontak2022]HSM

题目描述

递归定义超对称矩阵:

  • 每个 1×11\times1 矩阵都是超对称矩阵。
  • 对于 n>1n>1,一个 n×nn\times n 矩阵超对称,当且仅当它关于水平中轴、竖直中轴及两条主对角线均对称,并且令 d=⌊n/2⌋d=\lfloor n/2\rfloor 后,四个角上的 d×dd\times d 子矩阵均超对称。

二进制矩阵的每个元素为0或1。将矩阵从第一行到最后一行、每行从左到右读出,得到一个 n2n^2 位二进制整数,称为矩阵的值;允许前导零。

把所有 n×nn\times n 超对称二进制矩阵的值从小到大排列,求第 kk 小的值对 109+710^9+7 取模的结果。

输入格式

第一行一个十进制整数 nn。第二行给出 kk 的二进制表示,首位为1。

输出格式

输出所求值模 109+710^9+7 的结果。

数据范围

1≤n≤1091\le n\le10^9;1≤k≤210000001\le k\le2^{1000000},且保证 kk 不超过合法矩阵的数量。注意 kk 本身最多可以有 10000011000001 个二进制位。

子任务

子任务 附加限制 分值
1 n≤35 9
2 n≤1500 18
3 n≤100000 35
4 n≤1000000 27
5 无额外限制 11

样例 1

输入:

4
1

输出:

0

样例 2

输入:

3
100

输出:

186

说明

第二个样例 k=(100)₂=4,对应矩阵为 010 / 111 / 010,按行读出的二进制数为186。