说明

题目背景 

（背景里面的都是废话，想直接做题可以从题目描述开始看）

 注意：题目背景非真实历史

1936 年 4 月 巴黎 

和历史不一样的是，东面俄国的十月革命被战胜协约国后的德国血腥镇压，但是西面的法国那从一战战壕中开始的社会主义革命却成功了。 

和对十月革命的态度不同，德国皇帝威廉二世其实是支持这次革命的，因为把前共和国政府赶出法国本土（润到非洲去了）后，新生的法兰西公社联邦失去了所有殖民地，资源供给甚至需要依赖德国，德国希望以此彻底拿捏公社，断了复仇的想法。公社一度加入过以德国为首的中欧经济同盟。 

然而，英意两国的变动使得事情有了变化。1922 年，意大利发生革命，红军被奥地利挡在了波河以西，意大利由此被一分为四，然而革命者掌握了绝大部分北意工业区，西面还背靠公社；1925 年，海峡对岸的英国也发生了革命，温莎王朝被赶到加拿大。新生的意大利和英国随即和公社结盟。

随后的几年，世界各地都开始爆发革命。到 30 年代年初，各大洲都出现了掌握全国或者割据一方的革命政权。皇帝的脑门由此终于开始冒汗。随着西面公社对德复仇的声音越来越大，威廉二世这位在皇位上坐了 40 多年的人第一次感到局势要变得无法控制。 

另一方面，德国在一战后几乎独吞了同盟国的胜利成果，吃得太撑消化不良，这么一个并不合格的领头羊导致大战结束后的世界秩序陷入了前所未有的动荡。

 黑色星期一的发生终于让一切都绷不住了。经济和德国深度绑定的各国都开始陷入无尽的混乱中。在这样的背景下，各国的社会主义党派，甚至是殖民地里一些追求民族独立的有志人士都齐聚巴黎。他们一边交流各国目前的实际情况，向巴黎和伦敦寻求建议；一边将现在已经在英法意三国之间的外交，经济，军事，教育等各方面的合作机制进行扩大；一边开始统筹资源，准备燃起世界革命和民族独立之火。 

这次会议最紧急的议题是援助西班牙。虽然变动了一个世界线，但是西班牙的事情还是那么糟糕。内战即将爆发，会议参与方决定先向加泰罗尼亚地区的革命者输送一批武器装备。

题目描述 

总共有来自 n 个国家或政党的代表参加了 1936 年第三国际大会。

每个参会代表都愿意向西班牙捐助枪支。枪支将集中在马赛港，并一起输送到巴塞罗那。 

每个箱子固定可以装 x 支枪，大会希望最后送去西班牙的枪支能刚好装满若干个箱子。每个国家送来的枪支只会都送往西班牙，或者都不送往西班牙。 

大会想知道在这样的情况下有多少种不同装箱的方案。一杆枪都不送不被算作一种方案。 

（P.S. 虽然我也不知道大会为什么要好奇这个事情，难道不应该先去关心枪够不够用吗，但是问题既然是这么问的，大家就求解这个问题吧）

输入格式

第一行为两个数 n,x。 后面 n 行每一行为一个数 Ri ，即每个代表所在的国家能送来的枪支数量。

输出格式

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

样例

4 5
1
2
8
2

3

提示

对于 100% 的数据， 1≤N≤2000， 1≤x≤1000， 1≤Ri ≤10^5 。