题目内容

给定一个由数字 0 到 9 组成的字符串 $s$，你需要找出所有满足条件的非空子序列，称为“奇异子序列”。一个子序列被认为是奇异的，当且仅当：

1. 它不含前导零（单个数字 0 视为没有前导零），即若子序列长度大于 $1$，其第一个字符不能是 0；
2. 子序列中奇数数字的个数与偶数数字的个数不相等。

这里奇数数字指 1、3、5、7、9，偶数数字指 0、2、4、6、8。

请你计算奇异子序列的总数。由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

字符串的长度 $n$ 满足 $1 \le n \le 5 \times 10^3$。字符串 $s$ 仅由字符 0 到 9 构成。

输入描述

第一行输入一个整数 $n$，代表字符串的长度。 第二行输入一个长度为 $n$ 的字符串 $s$，由数字 0 到 9 组成。

输出描述

输出一个整数，表示奇异子序列的数量对 $10^9+7$ 取模后的结果。

样例1

输入

1
1

输出

1

说明

字符串长度为 1，唯一的非空子序列为 "1"。它不含前导零，且包含 1 个奇数数字和 0 个偶数数字，两者不相等，因此是奇异子序列。总数为 1。

样例2

输入

2
10

输出

2

说明

字符串 $s = \text{``10''}$，所有非空子序列有："1"、"0"、"10"。

• "1"：奇数个数 1，偶数个数 0，不相等，有效；
• "0"：单个 0，不含前导零，奇数 0 偶数 1，有效；
• "10"：第一个字符为 '1'，无前导零；包含 1 个奇数（'1'）和 1 个偶数（'0'），奇偶个数相等，不满足条件。 因此奇异子序列共有 2 个。

样例3

输入

3
123

输出

5

说明

字符串 $s = \text{``123''}$。子序列及判断：

• "1"：奇数 1 偶数 0 → 满足；
• "2"：奇数 0 偶数 1 → 满足；
• "3"：奇数 1 偶数 0 → 满足；
• "12"：奇数 1 偶数 1 → 不满足；
• "13"：奇数 2 偶数 0 → 满足；
• "23"：奇数 1 偶数 1 → 不满足；
• "123"：奇数 2 偶数 1 → 满足。 有效子序列为 "1", "2", "3", "13", "123"，共 5 个。

样例4

输入

4
2024

输出

12

说明

字符串 $s = \text{``2024''}$，全由偶数数字组成。 任何非空子序列的奇数个数均为 0，偶数个数等于子序列长度，因此奇偶个数不相等等价于长度不为 0。只需剔除那些以 '0' 开头且长度大于 1 的子序列。 总非空子序列数为 $2^4 - 1 = 15$。以位置 2 的 '0' 开头且长度大于 1 的子序列有 "02", "04", "024" 共 3 个，均为非法。 因此奇异子序列总数为 $15 - 3 = 12$。