AkariDaisukiDiv1 | Topcoder Archive

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

```
"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.
```
"a"
```
```
"b"
```
```
"c"
```
```
"x"
```
```
"abcdefghij"
```
```
1
```
```
Returns: 0
```
The answer can be zero.
```
"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.

"a"

"b"

"c"

"d"

"baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba"

Returns: 191690599

"a"

"x"

"y"

"b"

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

Returns: 1

"waai"

"akari"

"daisuki"

"usushio"

"id"

10000000

Returns: 127859200

"vfsebgjfyfgerkqlr"

"ezbiwls"

"kjerx"

"jbmjvaawoxycfndukrjfg"

"bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs"

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)2024, Topcoder, Inc. All rights reserved.