Count Sum Sequences

You are given an array values of distinct positive integers and a positive integer target.

Count the sequences of values that sum to exactly target. Each value may appear any number of times, and order matters: [2, 5, 2] and [2, 2, 5] are different sequences.

Return the count modulo 10^9 + 7.

Examples

Example 1

Input: values = [2,3,5], target = 9
Output: 8
Explanation: The sequences are [2,2,5], [2,5,2], [5,2,2], [3,3,3], [2,2,2,3], [2,2,3,2], [2,3,2,2] and [3,2,2,2].

Example 2

Input: values = [2,3,5], target = 1
Output: 0
Explanation: Every value exceeds 1, so no sequence sums to 1.