#P16078. [Oni2019]Hipersimetrie

    ID: 15289 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-等价类划分自相似递归结构双指针合并有序序列贡献法模逆元快速幂费马小定理增量维护

[Oni2019]Hipersimetrie

题目描述

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

  1. 任意 1×11\times 1 矩阵都是超对称矩阵;

  2. 当 N>1N>1 时,一个 N×NN\times N 矩阵是超对称矩阵,当且仅当同时满足:

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

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

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

一个二进制矩阵是指所有元素均为 00 或 11 的矩阵。

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

任务

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

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

输入格式

第一行包含一个整数 NN。

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

输出格式

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

数据范围

  • 1≤N≤1 000 000 0001\le N\le 1\,000\,000\,000;
  • 1≤K≤21 000 0001\le K\le 2^{1\,000\,000};
  • 保证对于给定的 NN,至少存在 KK 个 N×NN\times N 二进制超对称矩阵。

子任务

子任务 分值 限制
1 27 N≤1500N\le 1500
2 62 N≤1 000 000N\le 1\,000\,000
3 11 N≤1 000 000 000N\le 1\,000\,000\,000

样例

输入

3
100

输出

186

解释

K=1002=4K=100_2=4。

第 44 小的矩阵为:

0 1 0
1 1 1
0 1 0

按行读取得到二进制数:

010111010

其十进制值为 186186。