Problem Brief

String Transformation (Also for Infra Automation Intern)

INTERNOA

See Snowflake online assessment and hiring insights

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

1Example 1

Input

src = "ababab", target = "ababab", k = 1

Output

Explanation

Choose the suffixes "abab" and "ab" to transform src to target in a single operation.

2Example 2

Input

src = "aaaa", target = "aaaa", k = 2

Output

Explanation

All sequences of operations convert src to the target.

3Example 3

Input

src = "aaaa", target = "aaaa", k = 2

Output

Explanation

All sequences of operations convert src to the target.

Constraints

Limits and guarantees your solution can rely on.

2 ≤ length(src) ≤ 1000
2 ≤ length(target) ≤ 1000
1 ≤ k ≤ 10^6