当前没有测试数据。

题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, ..., a_n$ 和一个整数 $m$。

定义一个子序列是"完美子序列"，当且仅当：

1. 该子序列是严格递增的（即子序列中相邻元素在原序列中的位置递增，且元素值严格递增）。
2. 该子序列所有元素之和能被 $m$ 整除。

请计算有多少个非空的完美子序列，答案对 $10^9+7$ 取模。

输入格式

第一行输入两个整数 $n$ 和 $m$。

第二行输入 $n$ 个整数，表示序列 $a$。

输出格式

输出一个整数，表示完美子序列的数量，对 $10^9+7$ 取模。

样例 #1

输入

5 3
1 2 3 4 5

输出

6

样例 #2

输入

4 5
1 4 2 3

输出

2

数据范围

对于 $30\%$ 的数据，$1 \le n \le 20$。

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le m \le 100$，$1 \le a_i \le 1000$。