思路

本题的核心问题是计算给定乐谱的所有本质不同的合法演奏方式。由于乐谱由数字组成，表示按键的编号，且合法的演奏方式是按下按键后数字串中不含有不合法的按键组合。因此我们可以将其转化为动态规划问题。

动态规划思路：

我们使用动态规划来解决该问题。具体来说，我们定义一个数组 dp[i]，表示到第 i 个位置时的合法演奏方式的数量。

1. 初始化：
   • dp[0] = 1，表示没有按任何键时只有一种合法方式。

题目描述

游游有 $26$ 个按键的琴，按下第一个按键可以奏出 $a$，第二个按键可以奏出 $b$，...，第二十六个按键可以奏出 $z$。

现在给出了一个乐谱的演奏方式，由数字组成，包含 $[0,9]$，但由于不考虑空格致使游戏不允许输入的情况，例子如 $s = 12$，表示先按下第一个按键，然后按第二个按键，也可能按下第十二个按键。而对于对于$120$，只能先按下第一个键，然后再按第二十个按键，因为不存在第零个按键。

现在请你帮助游游计算有多少种本质不同的合适演奏方式。

对于两种演奏方式，只要存在一个位置的按键不同则认为是不同的演奏方式，由于结果可能很大，请对 $10^9+7$取模后输出。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 $T$($1$ < $T$ < $10$)代表数据组数,每组测试数据描述如下: 对于每一组测试数据: 第一行一个整数 $n$(1 < $n$ < $10^5$)。 第二行一个长度为 $n$ 的字符串 $s$，保证输入仅含数字 $[0,9]$

输出描述

输出共 $T$ 行，每行一个整数，表示本质不同的合法演奏方式，结果对$10^9+7$取模。

示例 1

输入

2
2
12
3
120

输出

2
1