奶牛飞盘队（Cow Frisbee Team）

题目描述

Farmer Han 开始玩飞盘之后，YDS 也想让奶牛们享受飞盘的乐趣，因此他准备组建一支奶牛飞盘队。

现有 N 只奶牛（1 ≤ N ≤ 2000），每只奶牛都有一个飞盘水准指数 Ri（1 ≤ Ri ≤ 100000）。

YDS 想要选择 1 只或多于 1 只 奶牛加入飞盘队，并且要求：

所有被选中的奶牛的水准指数之和必须是 幸运数字 F（1 ≤ F ≤ 1000） 的 倍数。

请你计算，共有多少种不同的组队方案。 结果对 10⁸ 取模输出。

输入格式

• 第一行输入两个整数

  N F
  

• 接下来 N 行，每行一个整数

  Ri
  

输出格式

输出一个整数，为所有满足条件的组队方案数，对 10⁸ 取余。

样例输入

4 5
1
2
8
2

样例输出

3

说明

样例中可能的合法组合为（下标从 1 开始）：

• {1, 3} → 1 + 8 = 9，不是 5 的倍数
• {1, 2, 4} → 1 + 2 + 2 = 5，是 5 的倍数
• {3} → 8，不是 5 的倍数
• {2, 4} → 2 + 2 = 4，不是 5 的倍数
• {1, 3, 4} → 1 + 8 + 2 = 11，不是 5 的倍数
• ……

在所有合法方案中，最终共有 3 种（根据题意结果为 3）。

。