The NLP enthusiasts of Hackerland are working on a string transformation algorithm. In a single operation, a string s can be transformed into another string by removing a suffix of the string and adding the removed suffix in front of the remaining string. For example, the string "abcd" can be transformed to "dabc" by removing the suffix "d" and adding it to the front of the remaining string "abc".
Given two strings src and target of lowercase English characters and an integer k, find the number of ways to transform the string src to the string target using the given algorithm in exactly k steps. Since the answer can be large, report it modulo 10^9 + 7.
Note: Two ways are considered different if the sequence of indices chosen for breaking the suffix is different at 1 or more steps.
Function Description
Complete the function getNumWays in the editor.
getNumWays has the following parameter(s):
- 1.
string src: the source string - 2.
string target: the target string - 3.
int k: the number of steps
Returns
int: the number of ways modulo 10^9 + 7
Example 1:
Input: src = "ababab", target = "ababab", k = 1
Output: 2
Explanation:Choose the suffixes "abab" and "ab" to transformsrctotargetin a single operation.
Example 2:
Input: src = "aaaa", target = "aaaa", k = 2
Output: 9
Explanation:All sequences of operations convertsrcto thetarget.
Example 3:
Input: src = "aaaa", target = "aaaa", k = 2
Output: 9
Explanation:All sequences of operations convertsrcto thetarget.
- 2 ≤ length(src) ≤ 1000
- 2 ≤ length(target) ≤ 1000
- 1 ≤ k ≤ 10^6
input:
output: