A22516.纸币问题 2

普及-

通过率:0%

时间限制:1.00s

内存限制:512MB

题目描述

你是一个非常有钱的小朋友。你有 nn 种面额互不相同的纸币,第 ii 种纸币的面额为 aia_i 并且有无限张,现在你需要支付 ww 的金额,求问有多少种方式可以支付面额 ww,答案对 109+710^9+7 取模。
注意在这里,同样的纸币组合如果支付顺序不同,会被视作不同的方式。例如支付 33 元,使用一张面值 11 的纸币和一张面值 22 的纸币会产生两种方式(1+21+22+12+1)。

输入格式

第一行两个正整数 n,wn,w,分别表示纸币的种数和要凑出的金额。
第二行一行 nn 个以空格隔开的正整数 $a_1, a_2, \dots a_n $ 依次表示这 nn 种纸币的面额。

输出格式

一行一个整数,表示支付方式的数量。

输入输出样例

  • 输入#1

    6 15
    1 5 10 20 50 100

    输出#1

    42
  • 输入#2

    3 15
    1 5 11

    输出#2

    39

说明/提示

满足 1n1031\le n\le 10^31aiw1041\le a_i \le w\le 10^4

首页