803. Word Break II — Count All Sentences (Modulo 10^9+7)

Given s and a dictionary, count the number of ways to segment s into dictionary words (mod 10^9+7). Each word can be reused. Input: JSON {s, words}.

Input: JSON {s, words}.

Output: Integer count mod 10^9+7.

Examples

Example 1

Input: {"s":"catsanddog","words":["cat","cats","and","sand","dog"]}
Output: 2
Explanation: 'cats and dog' and 'cat sand dog'.

Example 2

Input: {"s":"a","words":["a"]}
Output: 1
Explanation: One way.