Jewelry Necklace Expectation

Louis.PS is a shrewd jewel merchant who creates unique necklaces by visiting cities in a country, collecting beads made from the most popular material in each city. In a given country, each city is labeled with a lowercase letter representing its popular material. The country’s road network forms a tree (i.e. it is connected and acyclic), so that for any two different cities there is exactly one simple path between them. For any ordered pair of cities \( (u,v) \), let \( \mathit{Str}_{u,v} \) be the string obtained by collecting beads along the unique path from city \( u \) to city \( v \) (note that in general \( \mathit{Str}_{u,v} \) and \( \mathit{Str}_{v,u} \) can be different).

A special feature necklace is described by a feature string \( \mathit{EigenString}[1\ldots M] \) of length \( M \). The popularity of any necklace with string \( P[1\ldots L] \) is defined as the number of positions \( K \) (with \( 1 \le K \le M-L+1 \)) such that \[ \mathit{EigenString}[K\ldots K+L-1]=P[1\ldots L]. \] This number is denoted as \( \mathit{Popularity}(P) \).

The expected popularity for the country is then defined as

[ \mathit{Expectation} = \frac{\sum_{u,v}{\mathit{Popularity}(\mathit{Str}_{u,v})}}{N^2}, ]

where the summation is taken over all ordered pairs of cities \( (u,v) \) (including the cases where \( u = v \)). Your task is to compute \( \mathit{Expectation} \) for a given country.

inputFormat

The first line contains two integers \( N \) and \( M \) separated by a space, where \( N \) is the number of cities and \( M \) is the length of the feature string.

The second line contains a string of length \( N \) consisting of lowercase letters. The \( i\)-th character represents the popular material in city \( i \).

Each of the next \( N-1 \) lines contains two integers \( u \) and \( v \) indicating that there is a road directly connecting city \( u \) and city \( v \).

The last line contains the feature string \( \mathit{EigenString} \) of length \( M \), consisting of lowercase letters.

outputFormat

Output a single floating point number representing \( \mathit{Expectation} \). Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 3
aab
1 2
2 3
aab

1.000000