OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1339--Bq与子序列

1339: Bq与子序列

时间限制: 2 Sec  内存限制: 128 MB
提交: 92  解决: 27
[提交] [状态] [讨论版] [命题人:]

题目描述

Bq给你一个长度为n的数组，然后询问你这个数组里面有多少个子序列的和模k为零。
 答案对1000000007取模 。
子序列可以不连续，例如数组1 2 3的子序列有，空集、1、2、3、1 2、1 3、2 3、 1 2 3。

输入

第一行两个整数n，k分别代表数组长度和模数k 。（1<=n<=1e4  , 1<=k<=100 ）
随后一行n个正整数 。保证数组的值在int范围内 。

输出

输出数组里面有多少个子序列的和模k为零。

样例输入 Copy 

3 3
1 3 2

样例输出 Copy 

4

提示

样例解释：
4种子序列
空集
1 2
3
1 3 2


来源/分类

 
[提交] [状态]