[USACO09MAR] Cow Frisbee Team S（线性DP）

[USACO09MAR] Cow Frisbee Team S

题目描述

老唐最近沉迷于飞盘游戏, 约翰希望与之共度时光, 并计划由老唐家的 N 头奶牛组成一支队伍参与比赛.

每头奶牛的能力值均为整数。第i头奶牛的能力值是R_i（其中i=1,2,…,N）。球队成员数量必须至少为1且不超过N-1人（当球队人数超过N时不符合规定）。将整个队伍的能力总和视为各队员能力值之和

约翰对迷信有一定的信仰，在这种信仰下他特别选定了他的幸运数字为变量 F ，因此他要求所有参赛队的能力之和必须能够被整除于该数值。为了帮助他完成这一目标，请计算所有满足条件的队伍组合数量的具体数目是多少？需要注意的是由于这个数值可能会非常庞大因此只需输出结果对十亿次方取模后的余数值即可

输入格式

第一行：两个用空格分开的整数：N 和 F。

第二行到 N+1 行：第 i+1 行有一个整数 R_i，表示第 i 头奶牛的能力。

输出格式

第一行：单个整数，表示方案数对 10^8 取模的值。

样例 #1

样例输入 #1

    4 5 
    1 
    2 
    8 
    2

样例输出 #1

    3

提示

对于 100\% 的数据，$1