Problem Description
A letter tree is a rooted tree that each edge is assigned to a lowercase letter. Node 1 is always considered the root. When making a tour in the tree, one is only allowed to step "down". In other word, if you're now on some node of the tree, you can only make a step to one of its children nodes.
After you travel along a path in the tree, you will obtain a Path String, which is formed by the letters assigned to edges that you just move along. The string exactly records all edges in the order of your visit.
Now we're faced with the problem. Located at some node u on the tree, your task is to move for exactly m steps and obtain a maximal lexicographic Path String. In order to avoid the huge output, you're only required to output the hash code of the string after it is transformed into a 26-base number, where 'a' for 0, 'b' for 1, …, 'z' for 25. For instance, "bac" = (678)26 for 678=1×262+0×261+2×260.
Input
The input contains several test cases.
An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with an integer N(2≤N≤105), which denotes the number of nodes in the tree.
The following (N-1) lines describe the edges. An edge is described in the format of (u,v,c), which denotes an undirected edge between u and v with a lowercase letter c assigned.
The following line contains a single integer M(1≤M≤105), indicating the number of queries.
The following M lines, each with a pair of positive integers (u,m), describe the queries. (1≤m≤105)
The nodes are labeled from 1 to N.
Output
Output the hash code modulo 109+7 of the maximal lexicographic Path String for each query, one per line. If it's impossible to move for m steps, output IMPOSSIBLE.
Sample Input
1
6
1 2 a
1 3 b
2 4 c
2 5 b
2 6 c
3
1 1
1 2
3 1
Sample Output
1
2
IMPOSSIBLE
