题解

题面描述

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

• 新建一个空字符串 $t$；
• 对于原字符串 $s$ 中的第 $i$ 个字符 $s_i$：
  • 如果 $s_i$ 等于 $1$，则在 $t$ 的末尾插入字符串 "01"；
  • 如果 $s_i$ 等于 $0$，则在 $t$ 的末尾插入字符 "1"；
• 操作结束后，用字符串 $t$ 替换 $s$。

题目内容

对于给定的仅由字符‘$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)$ 取模后输出。

样例1

输入

3
01 2
10101 1
101 10

输出

5 
8
377

说明

对于第一组测试数据：

• 第一轮，字符串$t$="$1\ 01$"

• 第二轮，字符串$t$="$01\ 1\ 01$"

  综上，结束时字符串$s$的长度为$5$。

对于第二组测试数据：

• 第一轮，字符串$t$="$01\ 1\ 01\ 1\ 01$"

  综上，结束时字符串$s$的长度为$8$。