题目描述

在中国古代音乐传承中，有一套隐秘的“音律编码”用于记录琴曲。

该系统将 $26$ 个基本音符与英文字母 a 到 z 一一对应。

每个音符都有一个固定的位序值：

• a 对应 $1$
• b 对应 $2$
• …
• z 对应 $26$

一段乐谱可以通过将其每个音符替换为对应的位序值，并按顺序连接起来，转化为一段由数字组成的“音律编码”。

例如，琴曲片段 faf 转换过程如下：

• f 是第 $6$ 个字母 $\to 6$。
• a 是第 $1$ 个字母 $\to 1$。
• f 是第 $6$ 个字母 $\to 6$，最终得到编码 $616$。

然而，同一个编码可能对应多种不同的乐谱。例如，编码 $616$ 既可以解读为 faf ($6,1,6$)，也可以解读为 fp ($6,16$)。

现在，给定一段在残卷中发现的音律编码，请你计算共有多少种可能的原始乐谱解读方案。由于结果可能很大，请对 $10^9+7$ 取模。

输入格式

输入一个整数 $t$，表示有 $t$ 组测试数据。

接下来 $t$ 行，每行一串数字表示一段乐谱转化的音律编码。

输出格式

对于每组测试数据，输出一行，表示对应的解读方案数。

样例

1
616

2

1
200

0

2
123412
121212

6
13

数据范围

对于 $100$ 的数据，输入的音律编码长度不超过 $10^5$ 位。

数据保证，$1 \leq t \leq 10$，音律编码中仅包含数字字符。