2466: Another Letter Tree

A letter tree is given on this page (HDOJ 4601).

Another letter tree of N nodes is now given, where each node is assigned to a lowercase letter. When making a tour from a node to another, one should always follow the shortest path between them. That is, no nodes should be visited twice during his tour.

After one travels along a path, he will obtain a Path String formed by the letters assigned to nodes that he just moves past. The string exactly records all nodes in the order he visits.

Now we’re faced with the problem. Initially we have a string S₀ and totally Q queries each in a shape of (u, v). For each query, we make a tour from u to v and obtain a Path String S_uv , and your task is to calculate how many times that S₀ occurs as a subsequence of S_uv . For example, “ab” occurs 3 times in “abab” as a subsequence.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For instance, “abc” and “ec” are both subsequence of “adebc”, while “ba” and “ed” are not.

The answer might be large, and thus you’re only required to output it modulo 10007.

The input consists of several test cases. The number of test cases T (T<=5) occurs in the first line of input.

For each test case:
The first line consists of two integers N and Q(1<=N, Q<=50000), denoting the number of nodes and queries, respectively.
Each of the following N - 1 lines contains a pair of integers u, v(1<=u, v<=N ), denoting an edge between node u and v.
The following line contains a string of N lowercase letters, where the ith denotes the letter represented by the ith node.
The following line contains S₀(1<=|S₀|<=30).
The following Q lines describe all queries, each of which describes the start node u and destination node v.

For each query, output the required answer modulo 10007 in a line.

2
6 3
1 2
1 3
2 4
2 5
3 6
abbaaa ab
4 5
4 6
2 1
6 3
1 2
1 3
2 4
2 5
3 6
abbaaa aba
4 5
4 6
2 1

1
3
0
1
4
0