# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Personality Traits

By arnab_1810043 · Limits 2s, 512 MB

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

InputOutput
2 1 2
ab
a

2


The resulting strings are $ab$, $ba$.

InputOutput
2 3 1
aa
aaa

0


### Statistics

78% Solution Ratio

pathanFastest, 0.2s

ashikurrahmanLightest, 131 kB

antihashShortest, 1010B