题目内容

我们定义一个整数：倘若数字位中奇数数字的个数不等于偶数数字的个数，那么我们称这个整数是一个不平衡数。

现在给定一个由数字 $0$ 到 $9$ 组成的字符串，求解其中有多少子序列满足：这些子序列所代表的数是一个不平衡数，且不包含前导零。

由于答案可能很大，请将答案对 $(10^9 + 7)$ 取模后输出。

【名词解释】

子序列：从原序列中删除任意个（可以为零、可以为全部）元素得到的新的序列。

【提示】

本题中，如果您需要使用到除法的取模，即计算
$(p \times q^{-1} \mod M)$ 时， $q^{-1}$ 需要使用公式 $(q^{M-2} \mod M)$ 得到。

例如，计算 $\frac{5}{4} \mod M$

$\frac {4^{-1} = (4^{M-2} \mod M) = 250000002} {\left(\frac{5}{4} \mod M\right) = 5 \times 4^{-1} \mod M = 5 \times 250000002 \mod M = 250000003}$

输入描述

第一行输入一个整数 $n$ $(1 \leq n \leq 5 \times 10^3)$ ，代表字符串长度。

第二行输入一个长度为 $n$ ，由数字 $0$ 到 $9$ 组成的字符串 $s$ 。可能包含前导零。

输出一个整数，表示可以组成不平衡数的子序列数量。

输入

3
102

输出

输入

6
001119

输出

输入

7
0000000

输出