Problem Brief

String Formation (Also for AI/ML Software Engineer Intern :)

INTERNOA

See Snowflake online assessment and hiring insights

Given an array of strings, each of the same length, and a target string, construct the target string using characters from the strings in the given array in such a way that the indices of the characters used are in a strictly increasing sequence. Here, the index of a character is the position at which it appears in the string. Multiple characters can be used from the same string.

Determine the number of ways to construct the target string. Two constructions are considered different if either the sequences of indices they use are different or the sequences are the same but there exists a character at some index that is chosen from a different string. Return the value modulo (10^9 + 7).

Function Description

Complete the function numWays in the editor below.

numWays has the following parameters:

1. String words[n]: an array of strings
2. String target: the target string

Returns

int: an integer representing the number of ways, modulo (10⁹ + 7)

1Example 1

Input

words = ["valya", "lyglb", "vldoh"], target = "val"

Output

Explanation

There are 4 ways to construct the string "val" such that the indices will be in strictly increasing order. 1. Select the 1st character of "valya", the 2nd character of "valya" and the 3rd character of "valya". 2. Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "lyglb". 3. Select the 1st character of "valya", the 2nd character of "valya" and the 4th character of "vldoh". 4. Select the 1st character of "vldoh", the 2nd character of "valya" and the 3rd character of "valya".

2Example 2

Input

words = ["adc", "aec", "efg"], target = "ac"

Output

Explanation

There are 4 ways to reach the target: 1. Select the 1st character of "adc" and the 3rd character of "adc". 2. Select the 1st character of "adc" and the 3rd character of "aec". 3. Select the 1st character of "aec" and the 3rd character of "adc". 4. Select the 1st character of "aec" and the 3rd character of "aec".

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 10^3

1 ≤ length of words[i] ≤ 3000

All words[i] are of equal length per test case.

The sum of the lengths of all words[i] is ≤ 10^5.

1 ≤ length of target ≤ length of words[i]

All characters are lowercase English letters.