### 问题描述 给定小齐一个数字 $S$，可以用 $S+1$ 种方式将其表示为两个非负整数 $A$ 和 $B$ 的和。 当两个整数相加时，进位是从一列数字传递到另一列数字的数字。它是通过使用标准算法从右到左地将数字相加来进行的。例如，当将 $6$ 和 $7$ 相加得到 $13$ 时，"3" 写入相同的列，而 "1" 则传递到左边。 小齐知道哪些数字列在执行加法 $A+B=S$ 时会产生进位。请找出解的数量。 ### 输入格式 第一行包含一个整数 $S$。 第二行包含一个二进制数组，其长度等于 $S$ 的数字位数减去 $1$（最高有效位不产生进位）。这些值对应于数字的列，从最右边的列开始。产生进位的列由 $1$ 表示，不产生进位的列由 $0$ 表示。 ### 输出格式 在第一行上输出答案。 ### 样例输入 ``` 15 0 ``` ### 样例输出 ``` 12 ``` ### 评测数据规模 $10 \le S \le 10^{18}$。