有一行标记为 的方格 和一个长度为 的序列 。 最初，将 号方格涂成黑色，将其他 号方格涂成白色，并在 号方格下一颗棋子。
您可以重复下面的操作任意多次，可能是零次：
求操作结束时可以涂黑的方格的可能集合数，答案模 。
第一行一个整数 。
第二行 哥整数 。
输出答案。
样例输入
5 1 2 3 1 1
样例输出
8
样例解释
涂成黑色的方格可能有八组：
对于所有数据：