Description

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

Format

Input

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

Output

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

Samples

5
1 2 3 4 5
3

11

3
4 8 2
15

0

Limitation

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