問題文

文字 0, 1, ? からなる長さ N の文字列 S が与えられる．文字列の N + 1 個組 (t_0, t_1, \ldots, t_N) であって以下の条件をすべて満たすものの個数を 998244353 で割った余りを求めよ：

• t_0 は空文字列である．
• 各 i = 0, 1, \ldots, N - 1 に対し，t_{i+1} は，t_i に 0 または 1 を 1 個いずれかの場所に挿入して得られる文字列である．
• t_N は，S に現れる ? をそれぞれ 0 または 1 で置き換えて得られる文字列である．

制約

• 1 \le N \le 250\,000．
• S は 0, 1, ? からなる長さ N の文字列である．

部分点

• N \le 5\,000 を満たすデータセットに正解した場合は，10 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 90 点が与えられる．

入力例 1

3
01?

出力例 1

8

条件を満たす組 (t_0, t_1, t_2, t_3) は以下の 8 個である：

• t_0 が空文字列，t_1 が 0，t_2 が 00，t_3 が 010．
• t_0 が空文字列，t_1 が 0，t_2 が 01，t_3 が 010．
• t_0 が空文字列，t_1 が 0，t_2 が 01，t_3 が 011．
• t_0 が空文字列，t_1 が 0，t_2 が 10，t_3 が 010．
• t_0 が空文字列，t_1 が 1，t_2 が 01，t_3 が 010．
• t_0 が空文字列，t_1 が 1，t_2 が 01，t_3 が 011．
• t_0 が空文字列，t_1 が 1，t_2 が 10，t_3 が 010．
• t_0 が空文字列，t_1 が 1，t_2 が 11，t_3 が 011．

入力例 2

9
0??001011

出力例 2

32400

入力例 3

40
1111111111111111111100000000000000000000

出力例 3

88808106