题目链接：http://codeforces.com/problemset/problem/176/B
题意：
给你一个字符串a，然后给你一个字符串b

你可以选择a串的某个位置砍掉，然后再把那个串从后面接到前面

让你砍k次，问你有多少种砍法，从a串砍成b串

解法：

dp

dp[i][0]表示砍了i次的变成b串的方案数

dp[i][1]表示砍了i次的变成非b串的方案数

然后转移就好了，预处理一下有多少个开头是b串的

然后转转就好了

//CF 176B

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
long long dp[300010][2];
///dp[i][0]表示砍了i次的变成b串的方案数
///dp[i][1]表示砍了i次的变成非b串的方案数
string a, b;
int k;

int main()
{
 cin >> a >> b;
 scanf("%d", &k);
 if(a == b) dp[0][0] = 1;
 else dp[0][1] = 1;
 int x = 0;
 for(int i = 0; i < a.size(); i++){
 int flag = 1;
 for(int j = 0; j < a.size(); j++){
 if(a[(i+j)%a.size()] != b[j]){
 flag = 0;
 break;
 }
 }
 if(flag) x++;
 }
 for(int i = 0; i < k; i++){
 dp[i+1][0] = (x*dp[i][1] + (x-1)*dp[i][0])%mod;
 dp[i+1][1] = ((a.size()-x)*dp[i][0] + (a.size()-x-1)*dp[i][1])%mod;
 }
 printf("%d\n", dp[k][0]);
 return 0;
}