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 SS and TT and an integer kk. You can apply following operation on the string SS at most kk times.

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

Suppose the final string after applying operations is called XX. You have to calculate the number of distinct strings XX where TT is a subsequence of XX after applying at most kk operations on string SS. Number of operations for each XX is independent i.ei.e you can apply at most kk operations in each time of making XX.

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.ei.e ace is a subsequence of abcde while aec is not).

Input

The first line contains three integers nn, mm and kk (1n,m10,0k1000){(1 \le n, m \le 10, 0 \le k \le 1000)} -size of the string SS, size of the string TT and maximum number of operations respectively.

The second line contains string SS containing only lowercase English letters.

The third line contains string TT containing only lowercase English letters.

Output

Print a single integer - total number of such distinct strings XX where TT is a subsequence of XX after applying at most kk operations for each XX.

Samples

InputOutput
2 1 2
ab
a
2

The resulting strings are abab, baba.

InputOutput
2 3 1
aa
aaa
0

    Discussion

    Statistics


    78% Solution Ratio

    adnan_tokyEarliest, 2M ago

    pathanFastest, 0.2s

    ashikurrahmanLightest, 131 kB

    antihashShortest, 1010B

    Submit

    Login to submit

    Editorial

    This problem is straightforward. Generate all permutations of SSS, check is TTT is a subsequence and...

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.