String Transformation
You are given two strings s and t of equal length n. You can perform the following operation on the string s:
- Remove a suffix of
sof lengthlwhere0 < l < nand append it at the start ofs.
Return the number of ways in which s can be transformed into t in exactly k operations.
Since the answer can be large, return it modulo 10^9 + 7.
Example 1
Input
s = "abcd", t = "cdab", k = 2Output
2There are two valid sequences of operations: choosing the suffix from index 3 in both operations, or choosing the suffix from index 1 in both operations.
Example 2
Input
s = "ababab", t = "ababab", k = 1Output
2There are two suffix choices, from index 2 or index 4, that transform
s back into t in one operation.Constraints
- 2 <= s.length <= 5 * 10^5
- 1 <= k <= 10^15
- s.length == t.length
- s and t consist of only lowercase English alphabets.