Time Limit: 1000 MS Memory Limit: 512M


Description

Cxh第一回合天胡锁了3个一星斧王,但是斧王要cxh解决一个问题才愿意合成二星斧王,为了cxh的段位(骑士三),帮帮他吧!

斧王给出了一个长度为n字符串s,这个字符串只包含前9个小写字母,给出q个询问,询问s[l,r]中有多少本质不同的子序列(两个子序列p,q长度不同或者存在i使得),答案对1e9+7取模,

Input

输入:第一行一个字符串s,n<=100000,第二行一个整数q(q<=100000),接下来q行描述一个询问

Output

输出:输出q行,依次表示每个询问的答案

Sample Input

bba
1
1 3

Sample Output

5