J. Randomized String Matching Algorithm
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
babca
ba
2
Output
436731905
Input
acdacda
cdc
3
Output
389144385
Input
abacbacbabaddcabbcdacba
badbcbcbdbacaa
998244353
Output
110991665
Input
bbbbbbbbb
bbbbb
123456789
Output
1