‹ 上一题 下一题 ›

g6-07993. 方案数·大数取模 未做

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

题目描述

小杨在统计装箱方案:有 件物品,第 件重量为 ,每件只有一件,最多选一次。他想知道,选出物品的总重量恰好等于 的选法共有多少种,答案对 取模。

输入格式

第一行两个整数 。

第二行 个整数 。

输出格式

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

样例

输入 1

3 3
1 2 3

输出 1

2

与 两种。

数据范围

,,。

输入
输出

            
答案