start and goal of the same length n. In one move you cut a tail of length 1 to n − 1 off the current string and put it in front. For example, moving the tail cd of abcd gives cdab.
Count the ways to make exactly moves moves that turn start into goal. Two ways differ if at least one move uses a different tail length. The answer can be huge, so return it modulo 10⁹ + 7.start='abc', goal='abc', moves=2 → 2
A move carries a tail of length 1 or 2 to the front. To get back to abc in two moves, use 1 then 2 (abc → cab → abc) or 2 then 1 (abc → bca → abc).
start='abab', goal='abab', moves=1 → 1
Of the three possible tails, only moving ab leaves the string unchanged.
start.length ≤ 5·10⁵goal.length == start.lengthmoves ≤ 10¹⁵start and goal consist of lowercase English letters onlystart='abc', goal='abc', moves=2
2
Run checks the first 3 tests in your browser. Submit checks all 61 tests on the server, hidden ones included.