Counting Repeated Pattern Paths in a Tree

Given a tree \(T\) with \(n\) nodes, where each node carries a character from \(A\) to \(Z\), and a pattern string \(S\) of length \(m\) (also consisting of uppercase letters), count the number of ordered pairs \((u,v)\) (note that \((u,v)\) and \((v,u)\) are considered distinct) such that the string formed by the unique shortest path from node \(u\) to node \(v\) is exactly equal to an integer number of repetitions of \(S\). In other words, if the path string is \(X\), there should exist an integer \(k \ge 1\) such that \[ X = \underbrace{S\,S\,\cdots\,S}_{k\text{ times}} \] For example, if \(S = \text{PLUS}\), then repeating once gives \(\text{PLUS}\), twice gives \(\text{PLUSPLUS}\), and so on. Note that the repetition count must be an integer, so if \(S=\text{XYXY}\), the string \(\text{XYXYXY}\) is not valid.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \(n\) and \(m\), where \(n\) is the number of nodes in the tree and \(m\) is the length of the pattern string \(S\).
2. The second line contains a string of length \(n\), where the \(i\)th character represents the label of node \(i\).
3. Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) describing an undirected edge between nodes \(u\) and \(v\).
4. The last line contains the pattern string \(S\) of length \(m\).

You can assume that the tree is connected.

outputFormat

Output a single integer: the number of ordered pairs \((u,v)\) such that the string formed by the shortest path from \(u\) to \(v\) is exactly equal to one or more consecutive repetitions of the pattern string \(S\).

sample

3 1
AAA
1 2
1 3
A

9