283. Number of Ways to Form Target String (Modulo 10^9+7)

Given a list of equal-length words and a target string, count the number of ways to form target by choosing characters column by column. You may pick target[k] from any word's character at some column j, but columns must be chosen strictly increasing. Return the count modulo 10^9+7. Input: JSON {words, target}.

Input: JSON {words, target}.

Output: Integer — count mod 10^9+7.

Examples

Input: {"words":["acca","bbbb","caca"],"target":"aba"}
Output: 6
Explanation: Six ways using increasing columns.

Input: {"words":["abba","baab"],"target":"bab"}
Output: 4
Explanation: Four ways.

Constraints

• 1<=words.length<=1000
• 1<=target.length<=1000

Asked by