← 返回题目列表

AtCoder · yahoo_procon2019_qual_f

F. 通过

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

有 N 潜弹排成一排。 给你一个字符串 S 长度 N.The i- 前面的第一个 Snuke 有两个红球,如果 i- 第一个字符 S is 0;一个红球和一个蓝球,如果 i- 第一个字符 S is 1;两个蓝色球,如果 i- 第一个字符 S is 2.

Takahashi 有一个最初为空的序列。重复以下过程后求他可能有的序列数 2N 次,模数 998244353:

  • 每个同时拥有一个或多个球的 Snuke 选择一个球并将其交给他前面的 Snuke,如果他是该行中的第一个 Snuke,则将其交给高桥。
  • 高桥接球并将其放在他的序列的末尾。

约束

  • 1 \leq |S| \leq 2000
  • S 包括 0,1 和 2.

请注意,整数 N 未在输入中直接给出;它作为字符串的长度间接给出 S.


输入

输入由标准输入按以下格式给出:

S

输出

重复该过程后,打印高桥可能拥有的可能序列的数量 2N 次,模数 998244353.


样本输入 1

02

示例输出 1

3

高桥可能有三个序列: rrbb, rbrb 和 rbbr,其中 r 和 b 分别代表红球和蓝球。


示例输入 2

1210

示例输出 2

55

示例输入 3

12001021211100201020

示例输出 3

543589959