该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

$N$ 个方格排成一排，依次编号为 $1$ ~ $N$。

现在让你向方格中填数。你只能按以下方式填数：你选择一个包含偶数个方格且全部方格均未填数的区间，将该区间的前一半方格全部填 $1$，后一半方格全部填 $2$.

你可以按以上方式执行任意次填数操作。操作完成后，你将得到一个填数方案。

现在有一些要求：

给出一个长度为 $N$ 的字符串 $S$，如果 $S_i=$1 说明方格 $i$ 必须填 1，如果 $S_i=$2 说明方格 $i$ 必须填 2，如果 $S_i=$0 说明方格 $i$ 填 1 或 2 或 不填 均可。

问题是：按指定的填数方式操作完成并满足以上要求得到的填数方案有多少种？答案可能很大，你需要输出答案 $mod$ $(10^9+7)$。

两种填数方案不同，当且仅当存在一个方格在两种方案中填写的数字不同。

输入格式

第一行：一个整数 $N$。

第二行：一个长度为 $N$ 的字符串 $S$，仅可能包含 0, 1, 2 三种字符。

输出格式

一个整数，表示答案 $mod$ $(10^9+7)$。

输入样例

6
100002

输出样例

5

样例解释

操作两次：

• （1）选择区间 [1,2] 将方格 1 填写 1，方格 2 填写 2.
• （2）选择区间 [3,6] 将方格 3,4 填写 1，方格 5,6 填写 2.

得到一种填数方案：121122

其他四种可以得到的填数方案为：112212，120012, 111222, 121212。

数据范围

100% 的数据：$2 ≤ N ≤ 5 × 10^5$。其中：

• 10% 的数据：$N≤ 500$。
• 20% 的数据：$N≤ 10^4$。
• 30% 的数据：$S$ 中最多包含 $100$ 个非 0 字符。