Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Given a string S, concatenate it to itself N times, and call the result S'. Given a string T, you want to find the maximum number M such that T concatenated to itself M times is a subsequence of S'. String S consists of lowercase English letters and wildcard character &, which can be any lowercase English letter, and string T consists of only lowercase English letters.

Constraints

|S|, |T| \leq 7\,500
N \leq 10^{15}

Input Format

The first line of input contains string S.
The second line of input contains string T. The final line has a single integer, N.

Output Format

Output the value of M.

Sample Input 1

bab
aba
4

Sample Output 1

2

Sample Input 2

ba&
aba
4

Sample Output 2

3

Comments

There are no comments at the moment.