#P17754. shot
shot
题目描述
在马群中,大马的久久注视着小马.
那快乐的神态,曼妙的身材和矫健的步伐已经深深印在大马的心里.
在长久的犹豫之后,大马决定用自己优秀的射击技巧得到小马的注目.
射击场上有 只气球排成一排,大马会进行 次射击.
为了展现自己的射击技巧,大马每次会请小马选定一个气球 , 如果第 个气球没有被打破, 就会打破第 个气球, 否则,大马会随机选择左边或右边第一个没有被打破的气球进行射击(如果一边已经没有气球了,大马一定会射击另一边的气球).
但是,小马的目光并没有投向大马.它在思考:如果大马每次射击都保证击中,最后气球有多少种可能的被打破的状态呢?
大马的心在滴血.它决定请你帮它回答这个问题.
两种状态不同,当且仅当一个气球在一个状态中被打破,在另一个状态中没有被打破.
答案模 输出.
输入格式
从标准输入读入。
第一行两个整数 .
第二行, 个整数, 第 个整数为 .
输出格式
输出到标准输出。
一行一个整数,表示最终可能的状态数模 .
样例
样例输入 1
6 4
2 3 4 4
样例输出 1
2
数据范围
设 为第 个气球被选中的次数.
对于 的数据,
对于 的数据,
对于 的数据,
对于另 的数据, 只存在最多一个整数 满足
对于 的数据,