Count Strings with Given Score

You are given three integers \(n\), \(S\), and \(k\) along with a list of \(k\) integers representing score values. Your task is to count the number of sequences of length \(n\) such that the sum of the scores in the sequence is exactly \(S\). At each position of the sequence, you may choose any of the provided score values. Since the answer can be very large, output the result modulo \(10^9+7\).

Example:

Input:
2 3 3
1 2 3
Output:
2

</p>

In the example above, there are exactly 2 sequences of length 2 that sum to 3.

inputFormat

The input is given via standard input and consists of two lines.

• The first line contains three space-separated integers \(n\), \(S\), and \(k\), where \(n\) is the length of the sequence, \(S\) is the target sum, and \(k\) is the number of available score values.
• The second line contains \(k\) space-separated integers which represent the available score values.

outputFormat

Output a single integer via standard output representing the number of valid sequences of length \(n\) that sum to \(S\) modulo \(10^9+7\).

## sample

2 3 3
1 2 3

2