假设原来的字符串长度为$n$，把原来的字符串通过一步能产生的所有字符串看作一个集合，每个字符串看作一个点，这个集合共有$n-1$个点，再加上原来的字符串，共$n$个点。把一次操作看作一条边，如果一个字符串通过一次操作就可以变成另一个字符串，那么这两个字符串所代表的点之间连一条边。可以发现这$n$个点构成的图是一个完全图。

那么，问题就转化为：

在一个完全图中，从初始点$s$出发，走$k$步，最终走到$t$点，问有多少种走法？

首先，总的方案为：
$$tot = (n - 1)^k$$
这很好理解，因为无论我们处于哪个点，每一步都会有$n-1$种选择走下一步。

我们定义$dp[k]$为：从起点$s$出发，走$k$步，最终不停留在起点$s$的方案数。那么，如何转移？

正难则反。我们可以先求出从$s$出发，走$k$步，最终仍然停留在$s$的方案数。

假设我们只走$k-1$步，停留在了不同于$s$的任意一个点，这种情况的方案数为$dp[k-1]$，接下来，我们再走一步就可以回到点$s$，因此，从$s$出发，走$k$步，最终仍然停留在$s$的方案数为$dp[k-1]$。 故状态转移方程为：
$$dp[k] = (n-1)^k - dp[k-1]$$

另外，可以发现这$n$个点并非两两不同，也就是说有重复的字符串存在。

一个显然的事情是，从$s$出发，走$k$步，最终走到不同于$s$的任意一个点，方案数相同。

假设有除了起始点以外，有m个点所表示的字符串都是$s2$，由于最终落到哪个点的概率是相同的，那么最终的答案应为：
$$ans = dp[k] * m / (n-1)$$

最后，如果起始点所代表的字符串$s1$也等于$s2$，那么我们的答案应该加上“从$s$出发，走$k$步，最终仍然停留在$s$的方案数”，即$dp[k-1]$。

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, mod = 1e9 + 7;

string s1, s2;

int k, n;

int dp[N]; // dp[i]表示，走i步，最终不停在初始点的方案数 

int get(){ // 计算从s1变到s2，只用一步，有几种方法 
    string s3 = s1 + s1;
    n = s2.length();
    int cnt = 0;
    for(int i = 1; i < n; i++){
        if(s3.substr(i, n) == s2)cnt++;
    }
    return cnt;
}

int exgcd(int a, int b, int& x, int& y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main(){

    cin >> s1;
    cin >> s2;
    cin >> k;
    if(!k){
        if(s1 == s2)cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }
    int cnt = get();
    dp[1] = n - 1;
    int q = n - 1;
    for(int i = 2; i <= k; i++){
        q = q * (n - 1) % mod;
        dp[i] = (q - dp[i-1]) % mod;
    } 
    int x, y;
    int d = exgcd(n - 1, mod, x, y); //除法取模要求逆元
    int ans = (dp[k] * cnt % mod * x % mod + mod) % mod; //多取模，防止爆long long
    if(s1 == s2)ans = ((ans + dp[k-1]) % mod + mod)% mod;
    cout << ans << endl;
    return 0;
}