F. 1-05F.mob的科学麻将

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

不知不觉间,mob已经在盐中的肉体改造部待了一年了,体魄强健的他很快又发现了新的爱好——“麻将”!虽然mob是地球上超能力最为强大的少年,但当他与Saki,Teru等天才麻将少女对战时,他却由于执念从不使用超能力!但由于他无法像对手一样看破牌山,因此评估自己的配牌,决定本局究竟是进攻还是防守成了一件 非常重要的事情。mob很快找到了一种方法去量化自己的起手配牌价值,以下是他自己总结出的经验公式:

一套麻将有张牌,第张牌的点数为,这张牌的任何一个子集都是一种可能的“配牌”,mob会用以下方式决定拿到某种配牌时应该进攻还是防守: 设一种配牌所含有的牌的点数分别为(这是一种含张牌的配牌),设数列中某个子序列的价值为组成这个子序列的点数和,设一种配牌的价值为相应数列的所有非空子序列的价值的和

如:配牌,它的所有非空子序列有,其价值分别为,因此这个配牌的价值为

若一种配牌的价值是的倍数,那么称这个配牌为好的配牌。

问:一套麻将中有多少个子集是“好的配牌”

由于答案可能非常大,你只需要输出答案对 取模的结果

输入格式

第一行两个正整数

下面一行个正整数用空格隔开,第个正整数表示

输出格式

输出一行一个正整数表示答案

样例

样例输入1 样例输出1
3 8
1 2 3
2
样例输入2 样例输出2
3 2
1 1 1
4

数据范围与提示