题目描述

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $n$ 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 $i$ 头奶牛的能力为 $R_i$ 。飞盘队的队员数量不能少于 $1$、大于$n$。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 $F$ ，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。

输入格式

第一行，两个整数：$n$ 和 $F$。

接下来 $n$ 行，第 $i+1$ 行有一个整数 $R_i$ ，表示第 $i$ 头奶牛的能力。

输出格式

一行一个整数，表示最终答案。

提示

数据范围与约定

• 对于 $100\%$ 的数据，$1 \le n \le 2000$，$1 \le F \le 1000$ ，$1 \le R_i \le 10^5$ 。

## 题目描述

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $n$ 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 $i$ 头奶牛的能力为 $R_i$ 。飞盘队的队员数量不能少于 $1$、大于$n$。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 $F$ ，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。

## 输入格式

第一行，两个整数：$n$ 和 $F$。

接下来 $n$ 行，第 $i+1$ 行有一个整数 $R_i$ ，表示第 $i$ 头奶牛的能力。

## 输出格式

一行一个整数，表示最终答案。

## 提示

#### 数据范围与约定

- 对于 $100\%$ 的数据，$1 \le n \le 2000$，$1 \le F \le 1000$ ，$1 \le R_i \le 10^5$ 。