HZNU Training 3—M

M - Word Cut

Let's consider one interesting word game. In this game you should transform one word into another through special operations.

Let's say we have word w, let's split this word into two non-empty parts x andy so, that w = xy. A split operation is transforming word w = xy into word u = yx. For example, a split operation can transform word "wordcut" into word "cutword".

You are given two words start and end. Count in how many ways we can transform word start into word end, if we apply exactly k split operations consecutively to word start.

Two ways are considered different if the sequences of applied operations differ. Two operation sequences are different if exists such number i (1 ≤ i ≤ k), that in the i-th operation of the first sequence the word splits into parts x and y, in the i-th operation of the second sequence the word splits into parts a and b, and additionally x ≠ a holds.

Input

The first line contains a non-empty word start, the second line contains a non-empty word end. The words consist of lowercase Latin letters. The number of letters in word start equals the number of letters in word end and is at least2 and doesn't exceed 1000 letters.

The third line contains integer k (0 ≤ k ≤ 10⁵) — the required number of operations.

Output

Print a single number — the answer to the problem. As this number can be rather large, print it modulo 1000000007 (10⁹ + 7).

Example Input ab ab 2 Output 1 Input ababab ababab 1 Output 2 Input ab ba 2 Output 0 Note

The sought way in the first sample is:

ab  →  a|b  →  ba  →  b|a  →  ab

In the second sample the two sought ways are:

ababab  →  abab|ab  →  abababababab  →  ab|abab  →  ababab 【分析】 题意：给定一个初始字符串和目标字符串，每次的操作是对当前字符串随意分成两部分，然后把这两部分直接交换位置.问有多少种方案数可以使初始串在经过n步操作后变成目标串； 首先我们可以发现一点，模拟过几次之后可以发现...对长度为len的字符串经过一次变换后只会变成len-1个新串，而对这len-1个新串经过一次变换后，会变成1个原串以及len-2个新串 其实可以把这个原串想想成一个环...不管怎么操作，结果还是这个环...知道这个之后就比较好写了... 先预处理一下这个环中有多少个目标串计为x f[i][0]表示i次操作与目标串相同的方案数，f[i][1]表示i次操作与目标串不同的方案数 状态转移就是： f[i+1][0]=(x*f[i][1]+(x-1)*f[i][0])%MOD;   f[i+1][1]=(((len-x)*f[i][0])%MOD+((len-x-1)*f[i][1])%MOD)%MOD;  

【代码】 

#include <iostream> #include <cstdio> #include <cstring> #define MOD 1000000007 using namespace std; long long f[100000][2]; char a[1000],b[1000]; int main() { gets(a);gets(b); int len=strlen(a); if (strncmp(a,b,len)==0) f[0][0]=1;else f[0][1]=1; int x=0; for (int i=0;i<len;i++) { for (int j=0;j<len;j++) if (a[(i+j)%len]!=b[j]) goto out; x++; out:; } int n;scanf("%d",&n); for (int i=0;i<n;i++) { f[i+1][0]=(x*f[i][1]+(x-1)*f[i][0])%MOD; f[i+1][1]=(((len-x)*f[i][0])%MOD+((len-x-1)*f[i][1])%MOD)%MOD; } printf("%d\n",f[n][0]); }