Algorithms
Hard
2851
3024
String Transformation
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 s of length l where 0 < l < n and append it at the start of s.
   For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. 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 109 + 7.

Example 1:

Input: s = "abcd", t = "cdab", k = 2
Output: 2
Explanation:
First way:
In first operation, choose suffix from index = 3, so resulting s = "dabc".
In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:
In first operation, choose suffix from index = 1, so resulting s = "bcda".
In second operation, choose suffix from index = 1, so resulting s = "cdab".

Example 2:

Input: s = "ababab", t = "ababab", k = 1
Output: 2
Explanation:
First way:
Choose suffix from index = 2, so resulting s = "ababab".

Second way:
Choose suffix from index = 4, so resulting s = "ababab".


Constraints:

 * 2 <= s.length <= 5 * 105
 * 1 <= k <= 1015
 * s.length == t.length
 * s and t consist of only lowercase English alphabets.
"""
class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        
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 s of length l where 0 < l < n and append it at the start of s.
   For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. 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 109 + 7.

Example 1:

Input: s = "abcd", t = "cdab", k = 2
Output: 2
Explanation:
First way:
In first operation, choose suffix from index = 3, so resulting s = "dabc".
In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:
In first operation, choose suffix from index = 1, so resulting s = "bcda".
In second operation, choose suffix from index = 1, so resulting s = "cdab".

Example 2:

Input: s = "ababab", t = "ababab", k = 1
Output: 2
Explanation:
First way:
Choose suffix from index = 2, so resulting s = "ababab".

Second way:
Choose suffix from index = 4, so resulting s = "ababab".


Constraints:

 * 2 <= s.length <= 5 * 105
 * 1 <= k <= 1015
 * s.length == t.length
 * s and t consist of only lowercase English alphabets.


Please complete the code below to solve above prblem:
```python
class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        
```

my_solution = Solution()

test_input = { "s": "abcd", "t": "cdab", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 2

test_input = { "s": "ababab", "t": "ababab", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 2

test_input = { "s": "goxoq", "t": "dfqgl", "k": 244326024901249 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "ceoceo", "t": "eoceoc", "k": 4 }
assert my_solution.numberOfWays(**test_input) == 208

test_input = { "s": "ib", "t": "ib", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "ttttttt", "t": "ttttttt", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 7776

test_input = { "s": "aaaa", "t": "aaaa", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 6561

test_input = { "s": "meplrmeplr", "t": "eplrmeplrm", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 956594

test_input = { "s": "dsmn", "t": "smnd", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 7

test_input = { "s": "jjj", "t": "jjj", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 1024

test_input = { "s": "rrrrr", "t": "rrrrr", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 4

test_input = { "s": "fefe", "t": "fefe", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 9841

test_input = { "s": "pfly", "t": "wvqr", "k": 840550364246523 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "ltjwwltjww", "t": "jwwltjwwlt", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 2

test_input = { "s": "mb", "t": "mb", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "jjjjjjjjjj", "t": "jjjjjjjjjj", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 729

test_input = { "s": "oqytlmi", "t": "lmioqyt", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 239945

test_input = { "s": "hpcg", "t": "pcgh", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 61

test_input = { "s": "bqbqbqbqbq", "t": "bqbqbqbqbq", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 193710244

test_input = { "s": "ccccccccc", "t": "ccccccccc", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 2097152

test_input = { "s": "jjjjjjjjjj", "t": "jjjjjjjjjj", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 387420489

test_input = { "s": "qqqq", "t": "qqqq", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 19683

test_input = { "s": "loppaqg", "t": "nvbxtmh", "k": 104865546226045 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "qqqqqqqqqq", "t": "qqqqqqqqqq", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 729

test_input = { "s": "qsqsqsqsqs", "t": "qsqsqsqsqs", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 41

test_input = { "s": "nnnnn", "t": "nnnnn", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 1024

test_input = { "s": "klncccd", "t": "klncccd", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "qqqqq", "t": "qqqqq", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 262144

test_input = { "s": "qvxrlh", "t": "hqvxrl", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 2604

test_input = { "s": "uuuu", "t": "uuuu", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 19683

test_input = { "s": "sss", "t": "sss", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 128

test_input = { "s": "gggggggggg", "t": "gggggggggg", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 9

test_input = { "s": "ks", "t": "cj", "k": 400700574233583 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "lllllllll", "t": "lllllllll", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 32768

test_input = { "s": "uhixx", "t": "xxuhi", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 13

test_input = { "s": "vkrvkrvkr", "t": "rvkrvkrvk", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 21

test_input = { "s": "xtxtxtxt", "t": "xtxtxtxt", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 2882401

test_input = { "s": "nzybrhi", "t": "rhinzyb", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 6665

test_input = { "s": "ff", "t": "ff", "k": 4 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "ubagdasws", "t": "aswsubagd", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 14913081

test_input = { "s": "aaaaa", "t": "aaaaa", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 1048576

test_input = { "s": "iiiiiiiiii", "t": "iiiiiiiiii", "k": 4 }
assert my_solution.numberOfWays(**test_input) == 6561

test_input = { "s": "nnjqjmgome", "t": "gbfuecwlqc", "k": 359221508193514 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "slmzyj", "t": "slmzyj", "k": 4 }
assert my_solution.numberOfWays(**test_input) == 105

test_input = { "s": "vfyxl", "t": "vfyxl", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 209716

test_input = { "s": "sxzfvsxzfv", "t": "vsxzfvsxzf", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 16

test_input = { "s": "kalt", "t": "ltka", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 547

test_input = { "s": "jj", "t": "jj", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "bcriunp", "t": "criunpb", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 5

test_input = { "s": "rutmzyj", "t": "zyjrutm", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 6665

test_input = { "s": "vvvvv", "t": "vvvvv", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 64

test_input = { "s": "hlld", "t": "hlld", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 4920

test_input = { "s": "kctcsgswa", "t": "qfyyjeohe", "k": 966836940319300 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "otwqxmpktt", "t": "totwqxmpkt", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 478297

test_input = { "s": "kkkkkkk", "t": "kkkkkkk", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 279936

test_input = { "s": "iyl", "t": "iyl", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 22

test_input = { "s": "glao", "t": "ogla", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 14762

test_input = { "s": "jp", "t": "jp", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "uuuuuu", "t": "uuuuuu", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 78125

test_input = { "s": "achach", "t": "achach", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 3255209

test_input = { "s": "uuuuuuuu", "t": "uuuuuuuu", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 823543

test_input = { "s": "gjh", "t": "jhg", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 171

test_input = { "s": "cliuw", "t": "fphcn", "k": 647756904366432 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "zmcum", "t": "mzmcu", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "ll", "t": "ll", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "ccccc", "t": "ccccc", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 4

test_input = { "s": "rrrr", "t": "rrrr", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 3

test_input = { "s": "ih", "t": "hi", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "qfgihqrw", "t": "rwqfgihq", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 720600

test_input = { "s": "cd", "t": "cd", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "oooooooooo", "t": "oooooooooo", "k": 4 }
assert my_solution.numberOfWays(**test_input) == 6561

test_input = { "s": "wp", "t": "wp", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "rqq", "t": "nln", "k": 776508964349618 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "rr", "t": "rr", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "knwppsd", "t": "psdknwp", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 5

test_input = { "s": "epfeepfe", "t": "feepfeep", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 10088402

test_input = { "s": "wwwww", "t": "wwwww", "k": 9 }
assert my_solution.numberOfWays(**test_input) == 262144

test_input = { "s": "cdcdcdcd", "t": "cdcdcdcd", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 58825

test_input = { "s": "uphfr", "t": "fruph", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 3277

test_input = { "s": "cocococo", "t": "cocococo", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 171

test_input = { "s": "vhzjo", "t": "jovhz", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "bbbbbbbbbb", "t": "bbbbbbbbbb", "k": 1 }
assert my_solution.numberOfWays(**test_input) == 9

test_input = { "s": "pgnrstuh", "t": "yjzhldlg", "k": 618648276258027 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "cccccc", "t": "cccccc", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 3125

test_input = { "s": "kkkkkkk", "t": "kkkkkkk", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 216

test_input = { "s": "lxqqzsvej", "t": "svejlxqqz", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 57

test_input = { "s": "lllll", "t": "lllll", "k": 3 }
assert my_solution.numberOfWays(**test_input) == 64

test_input = { "s": "hhhhhhhhhh", "t": "hhhhhhhhhh", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 43046721

test_input = { "s": "gggg", "t": "gggg", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 243

test_input = { "s": "jj", "t": "jj", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "uuuuuuuuu", "t": "uuuuuuuuu", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 73741817

test_input = { "s": "qvx", "t": "vxq", "k": 8 }
assert my_solution.numberOfWays(**test_input) == 85

test_input = { "s": "nolnqlgqcs", "t": "jkguybcfcu", "k": 179216079747558 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "xpk", "t": "xpk", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 22

test_input = { "s": "xzoyb", "t": "bxzoy", "k": 5 }
assert my_solution.numberOfWays(**test_input) == 205

test_input = { "s": "krxjvvg", "t": "krxjvvg", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 6

test_input = { "s": "ks", "t": "sk", "k": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "s": "ty", "t": "ty", "k": 6 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "s": "otototot", "t": "totototo", "k": 7 }
assert my_solution.numberOfWays(**test_input) == 411772

test_input = { "s": "uoaowbdznp", "t": "npuoaowbdz", "k": 10 }
assert my_solution.numberOfWays(**test_input) == 348678440