<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:
        # https://leetcode.com/problems/string-transformation/solutions/4028800/python3-super-short-solution-o-n-logk-math-kmp/
        # find how many index can rotate s to t
        # use dp to calculatet the total number of ways
        # index_map = {letter: [] for letter in string.ascii_lowercase}
        MOD = 10 ** 9 + 7
        n = len(s)

        def f(k_):
            return (pow(n-1, k_, MOD) - pow(-1, k_)) * pow(n, -1, MOD)
            
        ans = 0
        if s == t:
            ans += (n - 1) * f(k - 1)
        ans += self.kmp(t[1:] + t[:-1], s) * f(k)
        return ans % MOD

    
    def kmp(self, text, word):
        cnt = 0
        z = self.calc_z(word)
        i = 0
        j = 0
        while i < len(text):
            if word[j] != text[i]:
                j = z[j]
                if j < 0:
                    i += 1
                    j += 1
                continue
            i += 1
            j += 1
            if j == len(word):
                cnt += 1
                j = z[j]
        return cnt
    
    def calc_z(self, s):
        z = [None for _ in range(len(s)+1)]
        z[0] = -1
        i = 1
        j = 0
        
        while i < len(s):
            if s[i] == s[j]:
                z[i] = z[j]
            else:
                z[i] = j
                while j >= 0 and s[i] != s[j]:
                    j = z[j]
            i += 1
            j += 1
        z[i] = j
        return z


        # # dp -- TLE
        # index = set([i for i in range(n)])
        # for j in range(n):
        #     new_index = set()
        #     for i in index:
        #         if s[(i + 1) % n] == t[j]:
        #             new_index.add((i + 1) % n)
        #     index = new_index
        # # print(index)
        # # return 0
        # p = len(index)
        # if p == 0: 
        #     return 0
        # others = n - p
        # if n - 1 in index:
        #     is_p, not_p = p - 1, others
        # else:
        #     is_p, not_p = p, others - 1
        # for i in range((k - 1) % MOD):
        #     new_is_p = (is_p * (p - 1) + not_p * p) % MOD
        #     new_not_p = (is_p * others + not_p * (others - 1)) % MOD
        #     is_p, not_p = new_is_p, new_not_p
        # return is_p

200