时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 50 M，其他语言100 M
64bit IO Format: %lld
题目描述
给出一颗n个结点n-1条边的树，再给出一个长度为n的字符串s，树上的每个点都表示一个字符，点i表示的字符是s[i]，其只包含大写拉丁字符。再给出q个查询，对于每个查询，会给出两个整数u,v,表示树上的两个点。对于每个查询你将从点v开始走最短路径走到点u，并按行走的顺序连接每个结点上的字符，形成一个新的字符串H,你需要计算字符串H中包含子串‘ABCBA’的个数。子串的定义就是存在任意下标a<b<c<d<e，那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”ABC”的子串有”A”、”B”、”C”、”AB”、”AC”、”BC”、”ABC”。
输入描述:
第一行两个数n，q。1<=n<=3e4,1<=q<=1e5。
第二行一个长度为n的字符串s。所有字符都为大写拉丁字符。
接下来n-1行每行两个数u,v表示点u和点v之间有一条边
接下来q行每行两个整数u,v。1<=u,v<=n。
输出描述:
对于每个查询输出一个整数表示点v到点u的路径上”ABCBA”子串的个数，每个答案占一行，答案对10007取模。
示例1
输入
复制
8 3
ABABCBAA
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3 7
2 3
1 8
说明
对于查询3 7，从结点7走到结点3，形成的字符串为ABCBA，子串ABCBA的个数为1
对于查询1 8，从结点8走到结点3，形成的字符串为AABCBABA，子串ABCBA的个数为6