g6-08116. 小卖部买糖 · 林老师的题库

题目描述

放学后小杨去小卖部买糖：店里有 $n$ 种糖果，第 $i$ 种每颗 $a_{i}$ 元，每种糖果都有很多颗，想买几颗买几颗。小杨想把钱正好花光，一共花 $N$ 元，只看每种糖果各买了几颗、不看购买的先后顺序。问一共有多少种买法。方案数可能很大，请对 $1 0^{9} + 7$ 取模后输出。

第一行两个整数 $n$ 、 $N$ 。

第二行 $n$ 个整数 $a_{i}$ ，表示每种糖果的单价。

一行一个整数，表示购买方案数对 $1 0^{9} + 7$ 取模的结果。

4 12
1 2 5 10

一共 $15$ 种买法，例如 $10 + 2$ 、 $5 + 5 + 1 + 1$ 、 $2 \times 6$ 都正好花 $12$ 元。

$1 \leq n \leq 100$ ， $1 \leq N \leq 1 0^{4}$ ， $1 \leq a_{i} \leq 1 0^{4}$ ，保证单价互不相同。