Let there be a tree of N vertices numbered 1 to N. On each node there is a single character, let the character on the i^th node be C[i]. Count the number of ways to select 2 distinct nodes i and j such that the string spelled out by the letters on the simple path from i to j C[i]...C[j] in any order can form a palindrome. Note that (i,j) and (j,i) are two different choices.

Input format

First line of input contains single integer N: The number of nodes in the tree.

Second line contains N space-separated lower-case English characters: The ith of which represents C[i].

Next N-1 lines contain 2 integers each, representing a single edge. It is guaranteed the given edges form a tree.

Output format

Output a single integer: the number of ways of selecting 2 distinct nodes i and j to satisfy conditions in the problem statement

Constraints

$1 \leq N \leq 100000$