题面描述

小红有一个长度为 $3$ 且仅由小写字母组成的字符串 $s(1)$。她想基于这个字符串，构造一个总共包含 $n$ 个字符串的序列 $s(1), s(2), \dots, s(n)$，要求如下：

1. 同质性：序列中每个字符串都与 $s(1)$ 的字母种类和对应数量相同（可视为 $s(1)$ 的任意排列）。
2. 接龙性：对于任意 $i$（$2 \leq i \leq n$），需满足 $s(i)$ 的首字母等于 $s(i-1)$ 的末字母。

请你计算，在给定初始字符串 $s(1)$ 和整数 $n$ 的条件下，满足上述要求的不同序列方案有多少种。若两种方案中存在某个位置的字符串不同，则视为两种不同方案。最终答案可能很大，请对 $10^9+7$ 取模后输出。

思路

题目内容

小红有一个长度为$3$的字符串$s[1]$。

她希望在其基础上增加$n-1$个字符串，使得对于任意$i∈[2,n]$都满足$s[i][0] = s[i- 1][2]$，且每个字符串的长度以及所包含的字母种类和对应的数量都相同，我们称这个$n$个字符串构成同质接龙串。

现在小红想知道在给定$s[1]$的基础上，构成的同质接龙串的共有多少种，当两种方案有一个位置的字符串不相同时，我们则认为是不同的方案。由于结果可能很大，对$10^9+7$取模后再输出。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数$T(1≤T≤10)$,代表数据组数,每组测试数据描述如下: 对于每一组测试数据:

一个长度为$3$、仅由小写字母构成的字符串$s[1]$ 和一个整数$n(1≤n≤10^5)$。

输出描述

对于每组数据，输出一个整数，表示方案总数，结果对$10^9+7$取模后输出。

样例1

输入

2
abc 2
abc 1

输出

2
1