You are given a string of length n and two alphabets x and y . There are q queries each has 2 integers l and r.you have to consider substring [l,r] of given string and count the number of distinct sub sequence of sub string which starts with x and ends with y.

Two substring are considered different if they starts and end with different indices.

count the number mod 1e7.

example

aabb

a b

0 2 ans = 3

1 3 ans=3

0 3 ans = 9