该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

大样例下载

题目背景

给你一个整数，你从其中任意取若干个（至少一个）数位上的数字，按原顺序排列组成一个新数，称该新数为原数的生成数。

例如，对于整数 12335，整数 1, 33, 125, 12335 等均为 12335 的生成数，但 4, 521, 2333 等均不是 12335 的生成数。

题目描述

给出一个整数 n，每位都是一个非零阿拉伯数字。

现在给出 m 个询问，每个询问给出两个整数 x 和 y，表示你只能从左数第 x 位到第 y 位的数位上取数字生成新数，问：你能得到多少个不同的生成数？输出答案 mod $(10 ^ 9 + 7)$。

注意：这里的第一位是指原整数的最高位，第二位是指次高位，最后一位则是指原整数的最低位即个位。

输入格式

第一行：一个整数 n，数据保证 n 中不含数字 0

第二行：一个整数 m

接下来 m 行：每行两个整数 x, y

输出格式

共 m 行，每个询问的答案占一行

样例输入

1232212
2
1 2
4 6

样例输出

3
5

数据范围

记 $len(n)$ 表示整数 $n$ 的位数。

20% 的数据：$len(n) ≤ 20$；

40% 的数据：$len(n) ≤ 10^3$；

60% 的数据：$len(n) ≤ 10^4$；

100% 的数据：$1 ≤ len(n) ≤ 10^5, 1 ≤ m ≤ 10^5, 1 ≤ x ≤ y ≤ len(n)$。