505006 - 字典

小光手上有一本字典存储了大量的单词，有一次，他把所有单词组成了一个很长很长的字符串string。现在麻烦来了，他忘记了原来的字符串都是什么，神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值，由以下公式计算得到：

公式中的数学符号∏，读作“派”，即π的大写、是求积符号，表示累项相乘。格式和∑一样，下面表示起始值，上面是终止值。Si代表 S[i] 字符的 ASCII 码。 请帮助小光计算大字符串中任意一段的哈希值是多少。

输入有多组测试数据，每组测试数据第一行是一个正整数N（1≤N≤1 000），代表询问的次数，第二行一个字符串（1≤len(string)≤100 000），代表题目中的大字符串，接下来N行，每行包含两个正整数a和b（1≤a，b≤len(string)），代表询问的起始位置以及终止位置。

对于每一个询问，输出一个整数值，代表大字符串从 a位到b位的子串的哈希值。