‹ 上一题 下一题 ›

g6-07995. 方案数·V 等于 0 未做

1000 ms 256 MB 测试点 ? 6级·0/1背包GESP-6方案数与取模

题目描述

小杨要清空一只箱子:有 件物品,第 件重量 ,每件只有一件,最多选一次。已知这次 ,求总重量恰好等于 的选法种数(对 取模)。其中 最多可达 。

输入格式

第一行两个整数 (保证 )。

第二行 个整数 。

输出格式

一行一个整数,方案数对 取模。

样例

输入 1

2 0
5 5

输出 1

1

数据范围

,,。

输入
输出

            
答案