/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
0, 1, ? からなる文字列 S,X,Y が与えられます。
以下の手順で得られる文字列を良い文字列と呼ぶことにします。
- x,y からなる列 t=(t _ 1,t _ 2,\ldots,t _ k) であって、t _ i=t _ {i+1}=y となるような整数 i\ (1\le i\lt k) が存在しないようなものを一つ選ぶ。
- t の各要素について、それが x なら文字列 X に、y なら文字列 Y に置き換えることで得られる列を s=(s _ 1,s _ 2,\ldots,s _ k) とする。s _ 1,s _ 2,\ldots,s _ k をこの順に連結した文字列を T とする。
- T に含まれる
?について、それぞれ0か1を選んで置き換える。
S に含まれる ? についてそれぞれ 0 か 1 を選んで置き換えることで得られる良い文字列の個数を 998244353 で割った余りを求めてください。
制約
- S,X,Y は
0,1,?からなる文字列 - 1\le |S|\le2000\ (ここで、|S| で S の長さを表す。)
- 1\le |X|\le8
- 1\le |Y|\le8
入力
入力は以下の形式で標準入力から与えられる。
S X Y
出力
答えを出力せよ。
入力例 1
?0??11?1? 0?1 ?1?
出力例 1
5
例えば、S に含まれる ? についてそれぞれ 0 か 1 を選んで置き換えることで得られる文字列 001111011 は良い文字列です。
手順を t=(x,y,x) から始めると、T={}0?1?1?0?1 となります。
T に含まれる ? をそれぞれ 0 か 1 に置き換えることで 001111011 を得ることができるので、001111011 は良い文字列です。
この他に、001011010, 001011011, 001011110, 001011111 の 4 つの文字列が条件を満たします。
これらの他に条件を満たす文字列は存在しないため、5 を出力してください。
入力例 2
0?10?1?01? ??? ?????
出力例 2
0
t において y が連続してはいけないことに注意してください。
入力例 3
????????????1???1??0??????1???????1????????1????????????????0 ?0?? ?
出力例 3
992356689
条件を満たす文字列の個数を 998244353 で割った余りを出力することに注意してください。
Score : 600 points
Problem Statement
You are given strings S,X,Y consisting of 0, 1, and ?.
A string that can be obtained by the following procedure is called a good string.
- Choose a sequence t=(t _ 1,t _ 2,\ldots,t _ k) consisting of x and y such that there is no integer i\ (1\le i\lt k) with t _ i=t _ {i+1}=y.
- Let s=(s _ 1,s _ 2,\ldots,s _ k) be the sequence obtained by replacing each element of t with the string X if it is x, and with the string Y if it is y. Let T be the string obtained by concatenating s _ 1,s _ 2,\ldots,s _ k in this order.
- Replace each
?in T with0or1of your choice.
Find the number, modulo 998244353, of good strings that can be obtained by replacing each ? in S with 0 or 1.
Constraints
- S,X,Y are strings consisting of
0,1, and?. - 1\le |S|\le2000 (Here, |S| denotes the length of S.)
- 1\le |X|\le8
- 1\le |Y|\le8
Input
The input is given from Standard Input in the following format:
S X Y
Output
Print the answer.
Sample Input 1
?0??11?1? 0?1 ?1?
Sample Output 1
5
For example, the string 001111011, which can be obtained by replacing each ? in S with 0 or 1, is a good string.
Starting the procedure with t=(x,y,x) gives T={}0?1?1?0?1.
By replacing each ? in T with 0 or 1, we can obtain 001111011, so 001111011 is a good string.
Besides this, the four strings 001011010, 001011011, 001011110, 001011111 satisfy the condition.
No other strings satisfy the condition, so print 5.
Sample Input 2
0?10?1?01? ??? ?????
Sample Output 2
0
Note that y must not appear consecutively in t.
Sample Input 3
????????????1???1??0??????1???????1????????1????????????????0 ?0?? ?
Sample Output 3
992356689
Note that you should print the number of strings satisfying the condition modulo 998244353.