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 $998244353$. It may be helpful to know that $998244353$ is prime and $998244353=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 1000$

$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 $998244353$.

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\}$.