在 EGOI 国，有 座电波塔沿东西方向排列，为国民提供互联网通信服务。电波塔从西向东依次编号为 到 。每座电波塔 （）具有以下功能：
对于两座满足 的塔 ，当满足 时，信息可从塔 传输到塔 。
EGOI 国政府将通信稳定性定义为满足顺序传输条件的非空子集数量。具体来说，如果子集 （）满足以下条件，则 满足顺序传输条件：
给定电波塔参数，计算符合条件的子集数量模 的结果。
输入按以下格式从标准输入给出：
输出一行，表示方案数模 的值。
3 0 1 3 2 3 3 2
5
8 2 1 3 5 1 6 7 7 5 5 2 2 1 3 1 1 6
36
10 3 1 5 2 3 2 4 5 4 10 7 7 9 4 3 3 7 7 7 6 5
109
考虑选择电波塔 的情况。
所以，这种选择方式不满足条件。
所以，这种选择方式满足条件。
满足条件的塔的选择方式有 这 种。因此，输出 。
此样例满足所有子任务的限制。
该样例满足子任务 的限制。
