JOIN

 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`
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