#g. *L9魔力药剂

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

哈利想要制作一种魔力药剂，为此他购买了n棵草药，每棵草药的魔力值可能不同。哈利必须从中挑选出若干棵草药（至少选择一棵），使得这些草药的魔力值总和恰好为k的倍数。请计算这批草药能挑选出多少种不同的组合满足这个条件？这个答案有可能很大，请将结果对10⁹取余后输出。时间限制:1s 内存限制：256MB

第一行包含一个整数n，表示草药的数量。第二行包含n个整数a1,a2,a3,...a_n,表示每棵草药包含的魔力值，整数之间以一个空格隔开。第三行包含一个整数k。

一个整数，表示满足要求的组合数量对10⁹取余后的结果。

5
1 2 3 4 5
3

3
4 8 2
15

数据范围：测试点1~10:1<=n<=2000,1<=a_i<=10⁵,1<=k<=1000。