<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:
        def power(p, x, e):
            """The O(log(e)) algorithm which returns x^e (mod p)"""
            base = x
            answer = 1
            while e:
                if e & 1:
                    answer = (answer * base) % p

                base = (base * base) % p
                e >>= 1

            return answer

        def inv(p, x):
            """The O(log(p)) algorithm, given p and x,
            returns the mod p inverse, i.e., a value y such that x * y = 1 (mod p)"""
            return power(p, x, p - 2)

        P = 10 ** 9 + 7
        MOD = 2 ** 63 - 25
        INV = inv(MOD, 26)

        char_dict = {chr(ord('a') + i): i for i in range(26)}  # 'a' -> 0, 'b' -> 1, ..., 'z' -> 25

        def new_hash(s):
            """Given a string s, returns a hash of s.
            We define the hash of s as (s[0] * 26^0 + s[1] * 26^1 + s[2] * 26^2 + ...) (mod MOD)"""
            answer = 0
            p = 1

            for c in s:
                answer = (answer + char_dict[c] * p) % MOD
                p = (p * 26) % MOD

            return answer

        ht = new_hash(t)  # Get the hash of t
        good = []  # Stores all the desired rotation.

        n = len(s)
        SH = (1 - power(MOD, 26, n)) % MOD  # SH = 1 - 26^n (mod MOD), see below.

        hs = new_hash(s)  # The hash of unrotated s

        # Goal, for each i, compare the hash of rotate(s, i) and t.
        # If hashes are the same, (with high probability) they are the same.
        for i in range(n):
            if hs == ht:
                good.append(i)

            # Iteration. Given the previous hash hs, compute the next (right) rotated hs.
			# In this question, right rotation is equivalent to left rotation.
            # Intuition for this: As an example,
            # Non-rotated: abcd, hash = a * 26^0 + b * 26^1 + c * 26^2 + d * 26^3
            # Rotated:     dabc, hash = a * 26^1 + b * 26^2 + c * 26^3 + d * 26^0
            # New hash = (Old hash) * 26 + d * (1 - 26^4)
            c = char_dict[s[n - 1 - i]]
            hs = (26 * hs + c * SH) % MOD

        if not good:
            return 0

        # The combinatoric problem: Given k, r
        # we want to find the number of x_1,..., x_k such that 0 < x_i < n for each x_i,
        # and x_1 + ... + x_k = r (mod n).
        # The answer would be the summation of all the r in good (number of rotations which make s = t)
        # Pleas refer to the article for more explanations.

        n_0 = 1 if good[0] == 0 else 0  # 1 if s == t; otherwise 0
        n_r = len(good) - n_0  # Number of valid nonzero shifts

        c_r_k = (power(P, n - 1, k) - (-1) ** k) * inv(P, n)  # Number of combinations when r != 0
        c_0_k = c_r_k + (-1) ** k  # Number of combinations when r = 0

        return (n_0 * c_0_k + n_r * c_r_k) % P
1104