<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:
    # ---- KMP Template----
    def computeLPSArray(self, pat):
        M = len(pat)
        lps = [0] * M

        # Length of the previous longest prefix suffix
        length = 0
        i = 1

        # Loop calculates lps[i] for i = 1 to M-1
        while i < M:
            if pat[i] == pat[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1] # no update on i
                else:
                    lps[i] = 0
                    i += 1
        return lps


    def KMPSearch(self, pat, txt):
        M = len(pat)
        N = len(txt)

        # Create lps[] that will hold the longest prefix
        # suffix values for pattern
        lps = self.computeLPSArray(pat)
        result = []

        i = 0  # index for txt
        j = 0  # index for pat
        while (N - i) >= (M - j):
            if pat[j] == txt[i]:
                j += 1
                i += 1

            if j == M:
                result.append(i - j + 1)
                j = lps[j - 1]
            elif i < N and pat[j] != txt[i]:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
        return len(result)
    # -----------------
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        MOD = 10**9 + 7
        ka = s == t
        kb = self.KMPSearch(t, s[1:] + s[:-1]) # (pattern, text), return how many ways
        n = len(s)
        # all methametics
        f = (pow(n-1, k, MOD) - pow(-1, k)) * pow(n, MOD-2, MOD)
        return ((ka+kb)*f + ka*(pow(-1, k)))%MOD

358