Problem F: UTF-8

UTF-8はマルチバイト文字を符号化する手法の一つである。

文字は計算機上ではバイト列として扱われる。英語だけであればラテンアルファベットおよび数字、記号を合わせても 1byteで表現できるが、残念ながら世界中で利用されている文字を1byteで表現することはできないため、複数のバイトを用いて文字を表す必要がある。

ここで例えば"あ"という文字に12354(0x3042)という2バイト列を割り当てたとき、そのままバイト列を並べると0x30,0x42と2文字なのか0x3042で1文字なのかが区別がつかない。

このため、マルチバイト文字符号化方式のUTF-8では始めの1バイト目で続くバイト列の長さが分かるようにすることにより、この問題を克服している。具体的なビットパターンは以下のようになる。

ここでxは0/1の任意のビットとする。またyも0/1の任意のビットとなるがどれか一つは1である必要がある。また全ての文字は1,2,3,4バイト文字のいずれかであるとする。

ここでyのビットが少なくとも一つは1であるという制約は以下のような理由による。 例えば'/'(0x2f)をバイト列にエンコードする際に0x2fと1バイトで符号化するないしは0xc0 0xafと2バイトで符号化する方法の二つがあるが、このような曖昧性を許すとセキュリティ上の脅威のもととなる可能性があるためである。

以上の話を聞いたあなたはUTF-8がどの程度の自由度があるのかが気になった。具体的には与えられたバイト列の一部のビットが不明な時にUTF-8として可能なバイト列の組み合わせがどの程度あるかということである。

このとき可能なバイト列の組み合わせの個数を求め、1,000,000で割った余りを出力せよ。

Input

N
b1
b2
...
bN

Nはバイト列の個数, b_iはバイト列である。 1 ≤ N ≤ 1000 を満たしている。 b_iは記号{0/1/x}が8個並んでいる。xはビットが不明であることを示している。

Output

可能なバイト列の組み合わせの個数を1,000,000で割った余りを出力せよ。

Notes on Test Cases

上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。

N が 0 のとき入力の終わりを示します。

Sample Input

1
xxxxxxxx
3
11100000
10x00000
10111111
3
11100000
10000000
10111111
4
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
0

Output for Sample Input

128
1
0
778240