题解

题面描述

给定一个仅由字符 $0$ 和 $1$ 组成的字符串 $s$ 和一个正整数 $n$ 。进行 $n$ 轮操作，每一轮按照如下规则构造一个新字符串 $t$ ：

新建一个空字符串 $t$ ；
对于原字符串 $s$ $s$ 中的第 $i$ $i$ 个字符 $s_i$ $s_{i}$ ：
- 如果 $s_i$ 等于 $1$ ，则在 $t$ 的末尾插入字符串 "01"；
- 如果 $s_i$ 等于 $0$ ，则在 $t$ 的末尾插入字符 "1"；

1000ms

Difficulty: 5

所属公司 : 阿里

算法与标签>动态规划

对于给定的仅由字符‘ $0$ ’和‘ $1$ ’组成的字符串 $s$ ，按照下方规则进行 $n$ 轮操作，每一轮:

新建一个为空的辅助字符串 $t$ ;
对于第 $i$ 个字符 $s_i$ ，如果 $s_i$ ≡‘ $1$ ’，在字符串 $t$ 结尾插入字符串" $01$ ";反之，如果 $s_i$ =‘ $0$ ’，在字符串 $t$ 结尾插入字符‘ $1$ ’。
将字符串 $t$ 赋值给 $s$ ，结束本轮。

求解，经过 $n$ 轮操作后，字符串 $s$ 的长度。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T (1≦T≦10^5)$ 代表数据组数，每组测试数据描还如下:

在一行上输入一个长度为 $1≦ len(s) ≤10^5$ ，仅由字符‘ $0$ ’和‘ $1$ ’组成的字符串 $s$ 。随后，输入一个整数 $n(1≦n≦10^{18})$ 代表操作轮数。

除此之外，保证单个测试文件的 $n$ 之和不超过 $3×10^5$ 。

对于每一组测试数据，新起一行。输出一个整数，代表经过 $n$ 轮操作后，字符串 $s$ 的长度。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

输入

输出

5 
8
377

对于第一组测试数据：

对于第二组测试数据：

编辑器加载中…

输入

预期输出（选填）