Submit solution

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.