火星计数法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

火星人的计数规则里只有a,b,c,d四个字母,计数规则从小到大是 a,b,c,d,aa,ab,ac,ad,ba,……。
给出来由a,b,c,d四种字母组成的火星数字,算出该数字是第几个(从1开始)。

Input

第一行输入一个数T代表测试用例组数(T<=200),接下来T组测试用例,每组测试数据为一个火星数字(长度小于100)。

Output

 对于每组测试用例,输出该火星数字代表多少(结果对10000007取模)。每行输出一个结果。

Sample Input

2
a
ab

Sample Output

1
6

Hint

 

Source

中国海洋大学第三届“朗讯杯”编程比赛高级组试题