We consider DNA sequences, which are strings consisting exclusively of the characters A, C, G, and T. We say that a string $s$ is a subsequence of a string $s'$ if $s$ can be obtained by deleting some (possibly zero) characters from $s'$. For example, AGG is a subsequence of TAGAAG, while AGGA is not.

For two strings $s_1, s_2$, we define their $m$-similarity as the number of sequences $w$ of length $m$ such that $w$ is a subsequence of $s_1$ if and only if $w$ is a subsequence of $s_2$. In other words, it is the number of sequences of length $m$ that are either subsequences of both strings or subsequences of neither.

Given strings $s_1, s_2$ and an integer $m$, calculate the $m$-similarity of $s_1$ and $s_2$.

Input

The input consists of three lines. The first two lines contain the sequences $s_1$ and $s_2$, respectively, each consisting of at least one and at most $1\,000\,000$ characters from the set {A, C, G, T}. The third line of the input contains an integer $m$ ($1 \le m \le 20$).

Output

Output a single integer: the $m$-similarity of strings $s_1$ and $s_2$.

Examples

Input 1

TCAGG
TAGAAG
2

Output 1

11

Note 1

To calculate the 2-similarity of the sequences TCAGG and TAGAAG, one must consider all $4^2 = 16$ possible two-letter sequences. Among them, three (CA, CG, and TC) are subsequences of only the first sequence, two (AA and GA) are subsequences of only the second, four (AG, GG, TA, TG) are subsequences of both sequences, and the remaining seven (AC, AT, CC, CT, GC, GT, and TT) are subsequences of neither. Thus, the sought 2-similarity is $4 + 7 = 11$.

Input 2

T
AG
3

Output 2

64