JOIN
Get Time

   Problem Statement  

 Problem Statement for AkariDaisukiDiv1

Problem Statement

    

Consider the following function:

f(X) = Waai + X + Akari + X + Daisuki

Here, X is a string and + denotes string concatenation. Waai, Akari and Daisuki are constant non-empty strings.



You are given 5 Strings Waai, Akari, Daisuki, S and F, and a int k.

Compute how many times F occurs in f^k(S) as its substring. (The notation f^k(S) means that f is applied to S exactly k times in a row. See Notes for a formal definition.) Since the number can be quite large, compute the number modulo 1,000,000,007.

 

Definition

    
Class:AkariDaisukiDiv1
Method:countF
Parameters:String, String, String, String, String, int
Returns:int
Method signature:int countF(String Waai, String Akari, String Daisuki, String S, String F, int k)
(be sure your method is public)
    
 

Notes

-Formally, we have f^1(X)=f(X) and for k greater than one we have f^k(X)=f(f^(k-1)(X)).
-String A is substring of B if A can be obtained by erasing some (possibly zero) characters from the beginning of B and some (possibly zero) characters from the end of B.
 

Constraints

-Waai, Akari, Daisuki, S, and F will contain between 1 and 50 characters, inclusive.
-Each character of Waai, Akari, Daisuki, S, and F will be a lowercase letter ('a'-'z').
-k will be between 1 and 10,000,000, inclusive.
 

Examples

0)
    
"a"
"b"
"c"
"x"
"axb"
2
Returns: 2
S = "x",

f(S) = "axbxc",

f^2(S) = f("axbxc") = "aaxbxcbaxbxcc".

This string contains the substring "axb" twice.
1)
    
"a"
"b"
"c"
"x"
"abcdefghij"
1
Returns: 0
The answer can be zero.
2)
    
"a"
"a"
"a"
"b"
"aba"
2
Returns: 4
S = "b",

f(S) = "ababa",

f^2(S) = f("ababa") = "aababaaababaa".

This string contains the substring "aba" four times. You must count overlapping substrings.
3)
    
"a"
"b"
"c"
"d"
"baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba"
58
Returns: 191690599
4)
    
"a"
"x"
"y"
"b"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
49
Returns: 1
5)
    
"waai"
"akari"
"daisuki"
"usushio"
"id"
10000000
Returns: 127859200
6)
    
"vfsebgjfyfgerkqlr"
"ezbiwls"
"kjerx"
"jbmjvaawoxycfndukrjfg"
"bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs"
1575724
Returns: 483599313

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 541 Round 1 - Division I, Level Two