Personality Traits

We live in a society where personality is a distant memory.

Nowadays personality is represented by strings. You are given two strings $S$ and $T$ and an integer $k$. You can apply following operation on the string $S$ at most $k$ times.

• Choose two adjacent characters of the string $S$ and swap them.

Suppose the final string after applying operations is called $X$. You have to calculate the number of distinct strings $X$ where $T$ is a subsequence of $X$ after applying at most $k$ operations on string $S$. Number of operations for each $X$ is independent $i.e$ you can apply at most $k$ operations in each time of making $X$.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none or all) of the characters without disturbing the relative positions of the remaining characters. ($i.e$ ace is a subsequence of abcde while aec is not).

Input

The first line contains three integers $n$, $m$ and $k$ ${(1 \le n, m \le 10, 0 \le k \le 1000)}$ $-$size of the string $S$, size of the string $T$ and maximum number of operations respectively.

The second line contains string $S$ containing only lowercase English letters.

The third line contains string $T$ containing only lowercase English letters.

Output

Print a single integer $-$ total number of such distinct strings $X$ where $T$ is a subsequence of $X$ after applying at most $k$ operations for each $X$.

Samples

Input	Output
2 1 2 ab a	2
The resulting strings are $ab$, $ba$.

Input	Output
2 3 1 aa aaa	0