Louis.PS is a shrewd jeweler whose necklaces are unique, largely due to his unconventional production methods. Every time Louis.PS arrives in a country, he chooses a path to traverse its cities. Upon reaching a city, he uses the material popular in that city to make a bead, and strings the beads together in the order the cities were visited to form a necklace. To ensure that the produced necklace does not suffer from competition between cities, the same city will not appear more than once in the path (because if a necklace uses more material from city A than from city B, its promotion in city B might be negatively affected). After years of consumer surveys, Louis.PS has mastered a method for judging how attractive a necklace is to consumers. Specifically, Louis.PS has identified the characteristics of necklaces popular with consumers and, based on this, has created a long necklace (which Louis.PS calls the "feature necklace"). For a necklace for sale, the more times it appears in the feature necklace, the more popular it is with consumers.

Considering the complexity of reality, we make appropriate simplifications. For each country, there are roads directly connecting certain cities, and for any two distinct cities, there is exactly one path connecting them (i.e., the country is connected and contains no cycles). For each city, we use a lowercase letter to represent the type of material popular in that city. Thus, we can represent a necklace with a string consisting only of lowercase letters. We call the string corresponding to the feature necklace the "feature string," denoted as EigenString[1..M], where $M$ is the length of the feature necklace. For a necklace, assume its corresponding string is $P[1..L]$, where $L$ is the length of the necklace. If there exists a positive integer $K$ such that EigenString[K..K+L-1] $= P[1..L]$, we say this necklace appears once in the feature necklace. The number of such positive integers $K$ is the number of times this necklace appears in the feature necklace, denoted as Popularity(P).

Louis.PS uses the mathematical concept of expectation to evaluate whether a country is suitable for jewelry collection. For a country containing $N$ cities, let $Str_{u,v}$ denote the string obtained along the path starting at $u$ and ending at $v$ (the strings $Str_{u,v}$ and $Str_{v,u}$ are generally different). Then:

$$Expectation = \frac{\sum_{u,v} Popularity(Str_{u,v})}{N^2}$$

For the following example (the solid lines in the figure indicate that the two endpoints are directly connected by a road): $N=3$, the popular material types are a, a, b respectively.

EigenString = "abaab" $Str(3,1)=ba$, $Popularity(ba)=1$ $Str(1,1)=a$, $Popularity(a)=3$ $Str(1,2)=aa$, $Popularity(aa)=1$ $Str(1,3)=ab$, $Popularity(ab)=2$ $Str(2,1)=aa$, $Popularity(aa)=1$ $Str(2,2)=a$, $Popularity(a)=3$ $Str(2,3)=aab$, $Popularity(aab)=1$ $Str(3,1)=ba$, $Popularity(ba)=1$ $Str(3,2)=baa$, $Popularity(baa)=1$ $Str(3,3)=b$, $Popularity(b)=2$

$$Expectation = \frac{1+3+1+2+1+3+1+1+1+2}{9} = \frac{5}{3}$$

For a country, Louis.PS wants to know the value of its $Expectation$, but the workload of calculating the expectation is too great. As an apprentice in the jewelry store, you certainly do not want to miss this rare opportunity to show off in front of your boss.

Input

The first line contains two integers $N, M$, representing the number of cities and the length of the feature necklace. The next $N-1$ lines each contain two integers $x, y$, indicating that city $x$ and city $y$ are directly connected by a road. Cities are numbered $1 \sim N$. The next line contains a string of length $N$ consisting only of lowercase letters, where the $i$-th character represents the material type popular in city $i$. The last line contains a string of length $M$ consisting only of lowercase letters, representing the feature string.

Output

Output a single integer, which is $N^2 \times Expectation$.

Examples

Input 1

3 5
1 2
1 3
aab
abaab

Output 1

15

Constraints

For 20% of the data, $M \le 1000$; For 40% of the data, $N \le 8000, M \le 50000$; For 100% of the data, $N, M \le 50000$.