<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 kmp(self, s, t):
        # 構造部分匹配表 pi 用於 KMP 演算法
        pi = [0] * len(t)
        res = []

        # 計算 t 的部分匹配表
        for i in range(1, len(t)):
            j = pi[i-1]
            while j > 0 and t[j] != t[i]:
                j = pi[j-1]
            if t[j] == t[i]:
                pi[i] = j + 1

        j = 0
        # 使用 KMP 演算法在 s 中查找 t 的所有匹配位置
        for i in range(len(s)):
            while j > 0 and s[i] != t[j]:
                j = pi[j-1]
            if s[i] == t[j]:
                j += 1
            if j == len(t):
                res.append(i - len(t) + 1)
                j = pi[j-1]

        return res

    def numberOfWays(self, s: str, t: str, k: int) -> int:
        n = len(s)
        M = 10**9 + 7

        # 獲取 s 的兩倍長度拼接後，與 t 匹配的位置
        pos = self.kmp((s+s)[:-1], t)

        # f_k[1] 表示 k 步轉換的總數，f_k[0] 表示無法達到 k 步的情況
        f_k = [0, 0]

        # 使用快速冪計算方法計算 f_k[1] 的值，根據公式推導出來的結果
        f_k[1] = (pow(n-1, k, M) - (-1)**k + M) * pow(n, M-2, M) % M
        f_k[0] = (f_k[1] + (-1)**k + M) % M

        # 計算最終結果，根據 pos 中的匹配位置，累加符合條件的 f_k 值
        result = sum(f_k[p > 0] for p in pos) % M
        return result

# 測試用例
if __name__ == "__main__":
    solution = Solution()
    
    # 測試用例 1
    s = "abcd"
    t = "cdab"
    k = 2
    print(solution.numberOfWays(s, t, k))  # Output: 2
    
    # 測試用例 2
    s = "ababab"
    t = "ababab"
    k = 1
    print(solution.numberOfWays(s, t, k))  # Output: 2
    
    # 測試用例 3
    s = "abcabc"
    t = "bcabca"
    k = 3
    print(solution.numberOfWays(s, t, k))  # 測試不同長度和操作次數的情況

    # 測試用例 4
    s = "aabbcc"
    t = "bccaab"
    k = 4
    print(solution.numberOfWays(s, t, k))  # 測試更長的字串

765