B. Menci 的序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

你有一个长为 nn 的序列,每个位置是 * 或者 +* 表示让变量加上自身,+ 表示让变量 +1+1

现在你要选出它的一个子序列(子序列即原序列中取出一些位置,顺序不变地拼成的序列),使得一个初始为 00 的变量在对子序列中的字符依次执行对应操作后2k2^k 取模所得结果尽可能大。求出最大可能的结果。

输入格式

第一行两个正整数 n,kn,k,表示序列长度以及模数为 2k2^k

第二行一个长为 nn 的字符串表示序列。

输出格式

一行一个正整数,为答案的二进制表示,不含前导零,但答案为 00 时要输出 00(而不是空串)

样例

样例输入

9 5
++*++***+

样例输出

11001

样例解释

有多种选法可以达到最大,如++*++**++++***+

数据范围与提示

对于所有数据,1n,k1061\le n,k\le 10^6

子任务编号 分值 nn \leq kk\leq 特殊限制
1 1515 500500 1010 -
2 1515 500500 500500 -
3 2020 10510^5 5×1035\times 10^3 -
4 2020 10610^6 10610^6 不存在两个相邻的 +
5 3030 10610^6 10610^6 -