100. 变换种类数

输入格式

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

• 数据点 1: $1 \leqslant L \leqslant 13$
• 数据点 2: $1 \leqslant L \leqslant 50$
• 数据点 3: $1 \leqslant L \leqslant 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$。