题目内容

给定一个仅由小写字母与 $?$ 组成的字符串 $s$ (长度为 $m$ )。求有多少个不同的仅由小写字母组成的字符串 $t$ (长度为 $n$ ) 满足以下条件：

1)对所有下标 $i(1≤i≤n)$，若 $s[i]≠?$，则 $t[i]=s[i]$；

2)任意相邻字符均不相同，即对所有 $i(1≤i<n)$，有 $t[i]≠t[i+1]$。

由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

输入描述

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

第一行输入一个整数 $n(1≤n≤10^5)$ ；

第二行输入一个长度为 $n$ 、且只由小写字母和 $?$ 构成的字符串 $s$ 。

保证所有测试中 $n$ 的总和不超过 $5×10^5$ 。

输出描述

对于每组测试数据，输出一行一个整数，表示满足条件的字符串数对 $10^9+7$ 取模的结果。

样例1

输入

5
3
a?b
2
??
4
a??a
4
aabb
4
abab

输出

24
650
600
0
1