100. 变换种类数

输入格式

第 1 行：整数 $T(1⩽T⩽100)$为问题数。
第 2~T+1 行：每行是一个问题的字符串 $s$ (长度为 $L$)。

• 数据点 1: $1⩽L⩽13$
• 数据点 2: $1⩽L⩽50$
• 数据点 3: $1⩽L⩽100$

输出格式

对于每个问题，在一行中输出满足条件变换种类数。由于答案可能很大，输出对 ${10}^9+7$ 取模后的结果。

3
1
011
123

0
6
9

提示

对于 s=123，变换有

• 1+2+3
• 1-2+3
• 1+2-3
• 1-2-3
• 123
• 12+3
• 12-3
• 1+23
• 1-23

共 $9$ 种，这 $9$ 个算式的计算结果全部能被 $2$ 或 $3$ 整除，因此符合条件的变换种类数是 $9$。