/*
  AOJ 2209
  Title:UTF-8
  @kankichi573
*/
#include <stdio.h>
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
int count_c(char dat[],char c,int from,int to)
{
  int i,ret;

  ret=0;
  for(i=from;i<=to;i++)
    ret += (dat[i]==c)?1:0;
  return(ret);
}
int match_1byte(char dat[])
{
  //printf("Patten1!\n");

  if(dat[0]=='1')
    return(0);
  return(1<<count_c(&dat[0],'x',1,7));
}
my_match(char c1,char c2)
{
  return((c1==c2)||(c1=='x'));
}
mystrncmp(char s1[],char s2[],int n)
{
  int i;
  for(i=0;i<n;i++)
    if(!my_match(s1[i],s2[i]))
      return(0);
  return(-1);
}
int match_2byte(char dat[])
{
  int ret,ret0,retx,ret1,ret2,ret3;

  //printf("Patten2!\n");

  if(mystrncmp(&dat[0],"110",3) && mystrncmp(&dat[8],"10",2))
    {
      retx=count_c(&dat[0],'x',3,6);
      if(ret1=count_c(&dat[0],'1',3,6))
	ret0=(1<<retx);
      else
	ret0=(1<<retx)-1;

      ret2=count_c(&dat[0],'x',7,7);
      ret3=count_c(&dat[8],'x',2,7);
      ret=ret0*(1<<(ret2+ret3));
      
      //printf("2byte y ret=%d %d %d %d %d\n",ret0,ret,ret1,ret2,ret3);
      return(ret);
    }
  else
    return(0);
}
int match_3byte(char dat[])
{
  int ret,ret0,retx,ret1,ret2;

  //printf("Patten3!\n");

  if(mystrncmp(&dat[0],"1110",4) && mystrncmp(&dat[8],"10",2) && 
     mystrncmp(&dat[16],"10",2))
    {
      retx=count_c(&dat[0],'x',4,7)+count_c(&dat[8],'x',2,2);
      if(ret1=count_c(&dat[0],'1',4,7)+count_c(&dat[8],'1',2,2))
	ret0=(1<<retx);
      else
	ret0=(1<<retx)-1;

      ret2 =  count_c(&dat[8],'x',3,7);
      ret2 += count_c(&dat[16],'x',2,7);
      ret=ret0*(1<<ret2);
      
      //printf("3byte y ret=%d %d %d\n",ret0,ret,ret2);
      return(ret);
    }
  else
    return(0);
}
int match_4byte(char dat[])
{  int ret,ret0,retx,ret1,ret2;

  //printf("Patten4!\n");

  if(mystrncmp(&dat[0],"11110",4) && mystrncmp(&dat[8],"10",2) && 
     mystrncmp(&dat[16],"10",2) && mystrncmp(&dat[24],"10",2))
    {
      retx=count_c(&dat[0],'x',5,7)+count_c(&dat[8],'x',2,3);
      if(ret1=count_c(&dat[0],'1',5,7)+count_c(&dat[8],'1',2,3))
	ret0=(1<<retx);
      else
	ret0=(1<<retx)-1;

      ret2 =  count_c(&dat[8] ,'x',4,7);
      ret2 += count_c(&dat[16],'x',2,7);
      ret2 += count_c(&dat[24],'x',2,7);
      ret=ret0*(1<<ret2);
      
      //printf("4byte y ret=%d %d %d\n",ret0,ret,ret2);
      return(ret);
    }
  else
    return(0);
}


int match(char dat[][8],int len)
{
  unsigned long long ret,ret1;
  
  if(len==0)
    return(1);
  ret1  = match_1byte(&dat[0][0]);

  if(ret1)
      ret=ret1*match(&dat[1][0],len-1);
  else
    ret=0;

  if(len>=2)
  {
    ret1 = match_2byte(&dat[0][0]); 
    if(ret1)
      ret += ret1*match(&dat[2][0],len-2); 
  }
  if(len>=3)
    {
       ret1 = match_3byte(&dat[0][0]); 
      if(ret1)
	ret += ret1*match(&dat[3][0],len-3); 
    }
  if(len>=4)
    {
       ret1 = match_4byte(&dat[0][0]); 
      if(ret1)
	ret += ret1*match(&dat[4][0],len-4); 
    }
        

  return(ret % 1000000);
}
int n;
char dat[1000][8];

main()
{
  int i;

  while(scanf("%d" ,&n) && n)
    {
      for(i=0;i<n;i++)
	scanf("%s",&dat[i][0]);
  
      //printf("dat=%s\n",dat);
      printf("%d\n",match(dat,n));
    }
  return(0);
}