Rank 161 the next year: the course of four solutions has three exams!

Last year's rank one: Ah! Ah! So let 160 be your rank!

There have been secret reports of cheating in the entrance exams. The text of frauds is a field that unfortunately is not in our hands, but we know about its encryption operations. Each cryptographic operation transforms one letter into another letter.

It should be noted that if there was a letter that was not converted into any other letter. There is no change in the field either.

The number of these operations
n
is n

We only know that the text of the cheats is a single string. 1 means that if the main text of the report equals the string
s
s and the decrypted text (obtained by performing consecutive operations) equal to the string y
c
be c We can from
c
c by performing the reverse operations to
s
s to reach

Doing the opposite of the operations means to start from the last operation and go to the first operation, and secondly, if in our operation
′
a
′
′
 a
′
 to
′
b
′
′
 b
′
 We converted, on the contrary,
′
b
′
′
 b
′
 to
′
a
′
′
 a
′
 we will convert For example, if these two transformations are all our operations:

a b
b c
Plain text
These two conversions (operations) will be the opposite:

b
b a
Plain text
For example above
"
a
a
"
"aa" is a single string of length two. Because if the main operations are performed on it, the result
"
c
c
"
is "cc" and if reverse operations on
"
c
c
"
"cc" is applied again to the same
"
a
a
"
"aa" we arrive. and
"
b
b
"
"bb" is not a single string! Because if the right operations are applied to it
"
c
c
"
"cc" is obtained and as we said
"
c
c
"
"cc" in performing reverse operations to
"
a
a
"
"aa" ends.

We want to see how many different modes these cheats (single strings) have with the specified length??

But unfortunately, a number of back-to-back operations have been added by mistake. therefore
q
q You will be asked three numbers for each question
t
,
l
,
r
t,l,r are given and you need to find the remaining number of strings of length 1
t
t on
1
e
9
+
7
1e9+7 assuming that the operations
l
l to
r
r are deleted Print.

input
In the first line of input number
n
n comes. Then in
n
In the next n line, there is a pair of letters in each line that indicates the operations. on the line
n
+
2
n+2th number
q
q is the number of questions and finally
q
q line, each of which indicates a question.

1
≤
n
,
q
≤
200

000
1 ≤ n, q ≤ 200 000

1
≤
t
≤
200

000
1≤t≤200 000

1
≤
l
≤
r
≤
n
1≤l≤r≤n

All input characters consist of lowercase Latin letters.

output
in
q
q Print the output line for each question and its answer.

Example
Sample entry 1
2
a b
b c
3
1 1 2
1 1 1
1 2 2
Plain text
Sample output 1
26
25
25
Plain text
In the first question, because there is no operation, any letter can be used.

In the second question, it is not possible to
"
c
"
used "c" as the input string because after the operation, i.e
"
c
"
"c" remains and if we do the opposite step of the operation, it becomes
"
b
"
will be "b".

In the third question, it is not possible to
"
b
"
Use "b" as input string.

Sample entry 2
7
c f
f
c
d
f b
f c
f b
4
1 3 5
2 3 5
1 2 6
1 4 4

Plain text
Sample output 2
23
529
24
23
Plain text