题目描述
给定一个长度为 $n$ 的有问号的 01 串，问号可以任意填 0 或 1，求每一种填法的 SAM 点数之和。注意空串代表的节点被包含在内。
输入格式
第一行包含一个整数 $n$。
第二行是一个长度为 $n$ 的字符串，包含 0，1 和 ?。
输出格式
一行一个整数表示答案。
样例数据
样例 1 输入
36
100101110001010010101000000111000100样例 1 输出
62样例 2 输入
36
?010?11?011??1?000??1?0?1??10?001?1?样例 2 输出
2064504样例 3 输入
10
??????????样例 3 输出
14972样例 4 输入
36
??10???0???0?1?????0?0??1????0???111样例 4 输出
1049055790数据规模与约定
保证对于全部数据，$1\le n\le 36$，字符串只包含 0，1 和 ?。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| 1 | 字符串只包含 0 和 1 |
$10$ |
| 2 | 字符串中 ? 不超过 $20$ 个 |
$10$ |
| 3 | 字符串只包含 ? |
$30$ |
| 4 | $50$ |