<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:        
        n = len(s)

        # KMP to know the valid rotations         
        def pFunction(v):
            n = len(v)
            p = [0]*n
            for i in range(1,n):
                j = p[i-1]
                while j > 0 and v[j] != v[i] :
                    j = p[j - 1]
                
                if v[j] == v[i]:
                    j+=1
                p[i] = j  
            return p
        
        def getValidRotations(a,b):
            tmp = b+"#"+a+a
        
            p = pFunction(tmp)    
            
            positions = []
            for i in range(n+1,len(tmp)):
                if p[i] == n:
                    rot = (i-(n-1))-(n+1)
                    if rot<n: 
                        positions.append(rot)
            return positions
                
        # Binary exponentiation 
        mod = 10**9 + 7
        def bin_pow(a,b):
            x = 1
            while b: 
                if b&1: 
                    x*=a 
                    x%=mod
                a*=a
                a%=mod
                b>>=1
            return x        
              
        # Modular inverse, since we have a division in our formula we need to use the modular inverse, we can use this mode since mod is a prime.
        def inv(x):
            return bin_pow(x,mod-2)        

        # v[i] says how many sequences we have for the remainder i with k operations
        v = []
        if k%2 == 0:
            v = [((bin_pow(n-1,k)-1)* inv(n)) %mod]*n
            v[0]+=1
            v[0]%=mod
        else:
            v = [((bin_pow(n-1,k)+1)* inv(n)) %mod]*n
            v[0]-=1
            if v[0]<0:
                v[0]+=mod
                
        ans = 0
        for p in getValidRotations(s,t): 
            ans+=v[p]
            ans%=mod
            
            
        return ans 
1081