<p>You are given two strings <code>s</code> and <code>t</code> of equal length <code>n</code>. You can perform the following operation on the string <code>s</code>:</p>

<ul>
	<li>Remove a <strong>suffix</strong> of <code>s</code> of length <code>l</code> where <code>0 &lt; l &lt; n</code> and append it at the start of <code>s</code>.<br />
	For example, let <code>s = &#39;abcd&#39;</code> then in one operation you can remove the suffix <code>&#39;cd&#39;</code> and append it in front of <code>s</code> making <code>s = &#39;cdab&#39;</code>.</li>
</ul>

<p>You are also given an integer <code>k</code>. Return <em>the number of ways in which </em><code>s</code> <em>can be transformed into </em><code>t</code><em> in <strong>exactly</strong> </em><code>k</code><em> operations.</em></p>

<p>Since the answer can be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcd&quot;, t = &quot;cdab&quot;, k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
First way:
In first operation, choose suffix from index = 3, so resulting s = &quot;dabc&quot;.
In second operation, choose suffix from index = 3, so resulting s = &quot;cdab&quot;.

Second way:
In first operation, choose suffix from index = 1, so resulting s = &quot;bcda&quot;.
In second operation, choose suffix from index = 1, so resulting s = &quot;cdab&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ababab&quot;, t = &quot;ababab&quot;, k = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
First way:
Choose suffix from index = 2, so resulting s = &quot;ababab&quot;.

Second way:
Choose suffix from index = 4, so resulting s = &quot;ababab&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>15</sup></code></li>
	<li><code>s.length == t.length</code></li>
	<li><code>s</code> and <code>t</code> consist of only lowercase English alphabets.</li>
</ul>

class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        # for normal chars(no pattern), dp[i] = dp[i-1] *(l-2) + dp[i-2]*(l-1), dp[1]=1,dp[2]=l-2，in pattern, 求出k=1 and k=2, then dp，上述不行，因为k非常大
        # if s==t, need cnt-1,cnt是重复字段的次数
        # if s!=t,need cnt
        # f(k) = f(k-1) * (cnt-1)(from s to t then to t) + ((n-1)^(k-1)-f(k-1)) *cnt,(n-1) ^(k-1)-f(k-1)means all possible thran from s, then minus from s to t, so not t to t, *cnt
        # then f(k) + f(k-1) = (n-1)^(k-1) * cnt, as f(k-1)+f(k-2)=(n-1)^(k-2)*cnt,then f(k)-f(k-2) = (n-1)^(k-2)*(n-2)*cnt,add是等比数列求和，分k为奇偶
        # f1+f0 = cnt, f1=cnt-f0(s==t)
        
        mod = 10 ** 9 + 7
        def kmp(s,t):
            cnt = 0
            ns = t+"*"+s+s
            stack = [0]
            for i in range(1,len(ns)):
                idx = stack[-1]
                while idx > 0 and ns[i] != ns[idx]:
                    idx = stack[idx-1]
                stack.append(idx + (ns[i] == ns[idx]))
            stack = stack[len(s)+1:-1]
            for i,num in enumerate(stack):
                if num == len(s):
                    #print(i,i - num + 1)
                    cnt +=1
            return cnt
        # print("kmp(s,t)",kmp(s,t))
        res = 0
        cnt = kmp(s,t)
        f0 = int(s==t)
        f1 = cnt - f0
        n = len(s)
        left = f0 if k % 2 == 0 else f1
        
        a1 = (n-2)*cnt if k % 2 == 0 else (n-2)*(n-1)*cnt
        q = (n-1) ** 2
        if q == 1:
            res = (a1 * (k//2) + left)%mod
        else:
            # res = ((a1 *(1-q**(k//2))//(1-q)) + left)%mod
            qk = pow(q, k // 2, mod)  # 计算 q^(k//2) % mod
            a1_term = (a1 * (1 - qk) % mod) * pow(1 - q, mod - 2, mod) % mod  # 使用逆元计算除法
            res = (a1_term + left) % mod
            
            
            # res = a1 * (pow(q, k // 2, mod-2) - 1) / (q - 1) + left
        # print("a1,q,cnt,f0",a1,q,cnt,f0)
        return int(res) % mod
        
1059