問題一覧 > 通常問題

No.2040 010-1 Deletion

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 38
作問者 : milkcoffee / テスター : nok0 riano
お気に入りにしたユーザー ProblemId : 8119 / 自分の提出
問題文最終更新日: 2022-08-09 18:13:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 356 (順位表) の他の問題:

Problem Statement

A string $T$ consisting of 0, 1 is called a good string if $T$ satisfies the following condition.

  • By repeatedly choosing one of the following operations and performing it on $T$ any number of times, $T$ can be made into the empty string.
    • Delete a string 1 contained in $T$. After the deletion, the string formed by joining the parts before and after it becomes the new $T$.
    • Delete a string 010 contained in $T$. After the deletion, the string formed by joining the parts before and after it becomes the new $T$.

For example, 0110 and 01011010 are good strings, but 000 and 0001 are not good strings.

You are given a string $S$ of length $N$ consisting of 0, 1, ?.
Find the number, modulo $998244353$, of ways to replace each ? with 0 or 1 such that the result is a good string.

Input

$N$
$S$

  • $1 \leq N \leq 1500$
  • $N$ is an integer.
  • $S$ is a string of length $N$ consisting of 0, 1, ?.

Output

Print the answer modulo $998244353$ as an integer.

Sample

Sample 1
Input
6
010???
Output
3

The result is a good string only for 010010, 010100, 010111.

Sample 2
Input
4
000?
Output
0

No good string can be made.

Sample 3
Input
1
?
Output
1

Sample 4
Input
40
???0????1???????1??????0????1???????1???
Output
883469710

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。