Your favourite local farmer firmly believes that aliens do, in fact, exist. Even more so, he is sure that they are trying to communicate with him - through crop circles, no less.
These circles are quite peculiar - they are shaped in the form of a tree, and it seems like each circle contains one letter. The farmer is absolutely convinced that the letters represent, in fact, a codified message - simply because he has dreamed of a string which might be found (or not) as a chain in the tree of crop circles.
Since it is hard to believe, you must verify this. Given this tree with N nodes, each of them containing a lowercase letter of the Latin alphabet, how often does the string that the farmer has dreamed of occur as a simple path?
The first line of input will contain an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of nodes, and a string $$$s$$$ of at least $$$1$$$ and at most $$$10^{5}$$$ characters, representing the string that the farmer has dreamed of. Note that the string only consists of lowercase Latin alphabet letters: namely, for any element of the string, $$$s_i$$$, it holds that ($$$'a'$$$ $$$\leq s_i \leq$$$ $$$'z'$$$).
The next line will contain another string $$$x$$$ of $$$N$$$ characters. Character $$$x_i$$$ represents the letter which is found at node $$$i$$$.
Next will follow $$$N-1$$$ other lines, each of them with two integers $$$a$$$, $$$b$$$ ($$$1 \leq a,b \leq N$$$). These lines represent that an edge is drawn from node $$$a$$$ to node $$$b$$$.
The output should only have one integer - the number of times the farmer's string has been found as a simple path in the given tree.
Two simple paths of the same length $$$k$$$: $$$x_1, x_2, ..., x_k$$$ and $$$y_1, y_2, ..., y_k$$$ are considered different if there is at least one $$$i$$$ such that $$$x_i$$$, $$$y_i$$$ are different.
13 aba babaabaaabbaa 1 2 1 7 1 9 2 3 3 4 3 5 6 7 7 8 9 10 10 11 11 12 11 13
14
