题目描述

Aki认为一个字符串是美丽的，需要满足下面几个条件：

• 这个字符串的长度必须是偶数
• 这个字符串前面一半是 $1$，后面一半是 $2$

现在Aki拿到一个只由 $1$ 和 $2$ 组成的字符串，请你帮他计算有多少个子序列构成的字符串是美丽的。

例如：$s = "1122"$，一共有 $5$ 个美丽的子序列串，挑选的位置分别是：

$$\{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{1, 2, 3, 4\}$$

由于答案可能很大，将计算结果对 $998244353$ 取模后输出。

输入格式

一个字符串，只包含 $1$ 和 $2$。

输出格式

一个数，代表美丽的子序列串数量，结果对 $998244353$ 取模。

样例

1122

5

数据范围

• 字符串长度在 $10^5$ 以内