It is well known that Wesley is bad at dynamic programming. Six months after the contest, Wesley learned that you can solve the original problem with a significantly better time complexity. He decided to create a new problem with tighter constraints. The only differences between this problem and the original are the bounds on ~N~ and ~K~, as well as the time and memory limits. In addition, there will not be language specific time limits.

You are given a tree with ~N~ vertices. Recall that a tree is a connected graph where there is exactly one path between any two vertices. Each vertex in this tree is assigned a colour, red or black. You are asked to determine the number of balanced subgraphs with exactly ~K~ vertices. A subgraph is considered to be balanced if all vertices are connected and there are at least ~2~ red vertices and ~2~ black vertices.

Wesley originally wanted you to output the full answer, but he decided to be nice and only ask you to output it modulo ~998\,244\,353~. It may be helpful to know that ~998\,244\,353~ is prime and ~998\,244\,353 = 119 \times 2^{23} + 1~.

For this question, a connected subgraph is a subset of the original vertices and edges that form a tree.

Constraints

~1 \le K \le N \le 1\,000~

~1 \le u_i, v_i \le N~

The graph is a tree.

Input Specification

The first line contains 2 integers, ~N~ and ~K~.

The next line contains a string of ~N~ characters, describing the colouring of the tree. Each character is either R or B. If the ~i^{th}~ character is R, then vertex ~i~ is red. Otherwise, it is black.

The next ~N-1~ lines describe the edges of the tree. Each line contains 2 integers, ~u_i~, ~v_i~, indicating an edge between ~u_i~ and ~v_i~.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the number of balanced subgraphs with exactly ~K~ vertices, modulo ~998\,244\,353~.

Sample Input 1

6 5
BBBRBR
1 2
2 3
2 4
3 5
2 6

Sample Output 1

2

Sample Explanation 1

The two balanced subgraphs of size ~5~ are ~\{1,2,3,4,6\}~ and ~\{2,3,4,5,6\}~.

Sample Input 2

5 4
RBRBR
1 2
2 3
2 4
2 5

Sample Output 2

3

Sample Explanation 2

The three balanced subgraphs of size ~4~ are ~\{1,2,3,4\}~, ~\{1,2,4,5\}~, and ~\{2,3,4,5\}~.