Question

Cafeteria Coupon Combinations

A cafeteria sells snack coupons in N pack sizes. Pack size C_i gives exactly C_i points, and each pack can be bought any number of times.

Count how many different combinations of packs can make exactly Target points. Two combinations are considered the same if they use the same number of packs of each size, regardless of order.

Print the answer modulo 10^9 + 7.

The hidden idea: process pack sizes one by one so that order does not get counted multiple times.

Input

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.

The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.

Output

Print a single integer — the number of combinations modulo KaTeX can only parse string typed expression.

Example

Example 1:
Input

3 5

1 2 5

Output

Explanation
The combinations are KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression.

Example 2:
Input

2 3

2 4

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions