<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>

#Consider transition:
#0是 自己到自己， 1是非自己到自己
# "ababab' -> 'ababab'   bababa ababab
# 1 to 0 :c+1
# 0 to 1 : n-1-c
# 1 to 1 : n-2-c
#   （c  c+1 ）
#  （n-1-c n-2-c  ）
def zf(s,k):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(z[i - l], r - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            l, r = i, i + z[i]
            z[i] += 1
    res = 0
    for i in range(1,n):
        if z[i]>=k: res+=1
    return res

def matrix_mul(A,B):
    res = [[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j]+=(A[i][k]*B[k][j]) 
                res[i][j]%=MOD
    return res
def matrix_pow(A,n):
    res = [[1,0],[0,1]]
    while n>0:
        if n&1:
            res=matrix_mul(res,A)
        A = matrix_mul(A,A)
        n>>=1
    return res


MOD = 10**9+7
class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        if len(t)!=len(s) or t not in s+s:
            return 0
        n = len(t)
        c = zf(t+t,n)-1
        A = [[c,c+1],[n-1-c,n-2-c]]
        An = matrix_pow(A,k)
        return An[0][0]%MOD if s==t else An[0][1]%MOD
        
1149