UTF-8 is one of the methods for coding multibyte characters.

Characters are treated as bytes on the computer. If it is only English, it can be expressed in 1 byte even if the Latin alphabet, numbers and symbols are combined, but unfortunately it is not possible to express the characters used all over the world in 1 byte, so the characters are expressed using multiple bytes. There is a need.

Here, for example, when a 2-byte string of 12354 (0x3042) is assigned to the character "a", if the byte strings are arranged as they are, it is indistinguishable whether it is 2 characters with 0x30,0x42 or 1 character with 0x3042.

For this reason, UTF-8, which is a multi-byte character encoding method, overcomes this problem by making it possible to know the length of the byte string that continues in the first byte. The specific bit pattern is as follows.

Byte length | Bit pattern
--- | ---
1 | 0xxxxxxx
2 | 110yyyyx 10xxxxxx
3 | 1110yyyy 10yxxxxx 10xxxxxx
4 | 11110yyy 10yyxxxx 10xxxxxx 10xxxxxx

Here, x is an arbitrary bit of 0/1. Also, y can be any bit of 0/1, but one of them must be 1. It is assumed that all characters are 1, 2, 3, or 4-byte characters.

Here, the restriction that at least one bit of y is 1 is due to the following reasons. For example, when encoding'/' (0x2f) into a byte string, there are two methods, 0x2f and 1-byte coding, or 0xc0 0xaf and 2-byte coding, but allowing such ambiguity is for security reasons. This is because it may be a source of threats.

After hearing the above story, you were wondering how much freedom UTF-8 has. Specifically, how many combinations of bytes are possible as UTF-8 when some bits of a given byte sequence are unknown.

At this time, find the number of possible combinations of byte strings and output the remainder divided by 1,000,000.

Notes on Test Cases

Multiple datasets are given in the above input format. Create a program that outputs each data set in the above output format.

When N is 0, it indicates the end of input.

<!-



Input


N
b1
b2
...
bN

N is the number of bytes and bi is the bytes. 1 ≤ N ≤ 1000 is satisfied. For bi, eight symbols {0/1 / x} are lined up. x indicates that the bit is unknown.

Output

Output the remainder of dividing the number of possible byte string combinations by 1,000,000.

Examples

Input

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


Output

128
1
0
778240


Input

1
xxxxxxxx


Output

128


Input

3
11100000
10x00000
10111111


Output

1


Input

3
11100000
10000000
10111111


Output

0


Input

4
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx


Output

778240
// UTPC2010 F. UTF-8

#include <iostream>
#include <vector>
#include <string>
#include <string.h>

using namespace std;

int main(){
	int n;
	string cmp[4] = {"0xxxxxxx", "110yyyyx10xxxxxx", "1110yyyy10yxxxxx10xxxxxx", "11110yyy10yyxxxx10xxxxxx10xxxxxx"};
	long long dp[1001];
	while(cin >> n, n){
		vector<string> vs(n);
		for(int i=0;i<n;i++) cin >> vs[i];
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for(int i=0;i<n;i++){
			string cur;
			for(int j=0;j<4&&i+j<n;j++){
				cur += vs[i+j];
				int mul = 1;
				bool one = false;
				bool zero = true;
				bool seen = false;
				for(int k=0;k<cur.size();k++){
					if(isdigit(cmp[j][k])&&cmp[j][k]!=cur[k]&&cur[k]!='x') mul = 0;
					if(cmp[j][k]=='y'){
						if(cur[k]=='1') one = true;
						if(cur[k]!='0') zero = false;
						if(cur[k]=='x') mul *= 2;
					}
					if(cmp[j][k]=='x'){
						if(j!=0&&!seen){
							if(zero) mul = 0;
							if(!one&&mul>1) mul--;
							seen = true;
						}
						if(cur[k]=='x') mul = (mul*2)%1000000;
					}
				}
				dp[i+j+1] = (dp[i+j+1]+dp[i]*mul)%1000000;
			}
		}
		cout << dp[n] << endl;
	}
}