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


MOD = 10**9 + 7

class Solution:

  def _matmul(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    n = len(A)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
      for j in range(n):
        res[i][j] = sum(A[i][k] * B[k][j] for k in range(n)) % MOD
    return res

  def _matrix_exp(self, M: List[List[int]], n: int) -> List[List[int]]:
    res = [[0] * i + [1] + [0] * (len(M) - i - 1) for i in range(len(M))]
    while n:
      if n % 2 == 1:
        res = self._matmul(res, M)
      M = self._matmul(M, M)
      n //= 2

    return res

  def z_function(self, s):
    z, l, r = [0] * len(s), 0, 0
    for i in range(1, len(s)):
      if i < r:
        z[i] = min(r - i, z[i - l])

      while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
        z[i] += 1

      if i + z[i] > r:
        l = i
        r = i + z[i]

    return z

  def num_repeats(self, s):
    z = self.z_function(s)
    for i in range(len(s)):
      if i + z[i] >= len(s):
        return len(s) // i
    return 1

  def numberOfWays(self, s1: str, s2: str, k: int) -> int:
    if s2 not in s1 + s1:
      return 0

    num = min(self.num_repeats(s1), self.num_repeats(s2))
    M = [[len(s1) - 2, len(s2) - 1], [1, 0]]
    if k == 1:
      return M[1][0] * num - (s1 == s2)

    M_ = self._matrix_exp(M, k - 1)
    delta = -(s1 == s2) if k % 2 == 1 else (s1 == s2)

    return (M_[0][0] * num + delta) % MOD
1126