<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:
        MOD=1_000_000_007 
        def matrix_multiply(A, B):
            # Get the dimensions of the matrices
            num_rows_A, num_cols_A = len(A), len(A[0])
            num_rows_B, num_cols_B = len(B), len(B[0])

            # Check if the matrices can be multiplied
            if num_cols_A != num_rows_B:
                raise ValueError("Matrix dimensions are not compatible for multiplication.")

            # Create an empty matrix to store the result
            C = [[0] * num_cols_B for _ in range(num_rows_A)]

            # Perform matrix multiplication
            for i in range(num_rows_A):
                for j in range(num_cols_B):
                    for k in range(num_cols_A):
                        C[i][j] += A[i][k] * B[k][j]
                    C[i][j]%=MOD
            return C
        
        cache={}
        
        def binary_exponent(a,x):
            if x in cache:return cache[x]
            power=1
            res=a
            cache[1]=a
            while power*2<=x:
                res=matrix_multiply(res,res)
                power*=2
                cache[power]=res
            return res
        
        def exp_helper(a,x):
            res=0
            while x:
                power=pow(2,int(log(x,2)))
                curr=binary_exponent(a,power)
                if not res:res=curr
                else:res=matrix_multiply(res,curr)
                x-=power
            return res
            



        n = len(s)
        k_0=[[1],[0]]
        res=matrix_multiply( exp_helper([[0,n-1],[1,n-2]],k) , k_0)
        string=t+'$'+s+s
        z=[0]

        ans=0

        l, r, k = 0, 0, 0
        for i in range(1, len(t)+len(s)+1):
            if i > r:
                l, r = i, i
                while r < len(string) and string[r - l] == string[r]:
                    r += 1
                z.append(r - l)
                r -= 1
            else:
                k = i - l
                if z[k] < r - i + 1:
                    z.append(z[k])

                else:
                    l = i
                    while r < len(string) and string[r - l] == string[r]:
                        r += 1
                    z.append(r - l)
                    r -= 1
            if z[i]==len(t):
                if i==len(t)+1:
                    ans+=res[0][0]
                else:
                    ans+=res[1][0]
                ans%=MOD
            
        return ans
1172