<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, t: str, p: str) -> List[int]:
        # compute pi
        # pi[i] is the largest number smaller than i s.t. p[:pi[i]+1] is a suffix of p[:i+1]
        pi = [-1] * len(p)
        for i in range(1, len(p)):
            # pi[i] = pi^{k}[i-1]+1, where k is the smallest number s.t. p[pi^{k}[i-1]+1] = p[i]
            # pi^{k}[i-1] = pi[pi[pi[...[pi[i-1]]]]]
            # if there's no such k, pi[i] = -1
            k = pi[i - 1]
            while k >= 0 and p[k + 1] != p[i]:
                k = pi[k]
            pi[i] = k + 1 if p[k + 1] == p[i] else k

        k = -1  # store the position in p to match t[i]
        res = []
        for i in range(len(t)):
            # find the next position in p to match t[i]
            while k >= 0 and p[k + 1] != t[i]:
                k = pi[k]
            # if such position exists, increment k
            if p[k + 1] == t[i]:
                k += 1
            # if matched, store the starting position in t, and k jumps back to previous position
            if k == len(p) - 1:
                res.append(i - len(p) + 1)
                k = pi[k]

        return res

    def occurrence(self, s: str, t: str) -> List[int]:
        return self.kmp(s+s[:-1], t)

    def numberOfWays(self, s: str, t: str, k: int) -> int:
        occ = self.occurrence(s, t)
        n = len(s)
        M = 10**9 + 7
        other_ways = ((pow(n-1, k, M) - (-1)**k + M) * pow(n, M-2, M)) % M
        matched_ways = other_ways + (-1)**k
        ways = [matched_ways, other_ways]
        return sum(ways[not not i] for i in occ) % M
901