Description

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

Format

Input

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

Output

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

Samples

5
1 2 3 4 5
3

11

3
4 8 2
15

0

Limitation

1s, 1024KiB for each test case.