You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get. 

Sample Input

Sample Output

 #include <stdio.h>

 #include <string.h>

 #define maxn 300

 int str1[maxn][maxn];

 int main()

 {

     int T, i, j;

     scanf("%d ",&T);

     while(T--)

     {

         char str[];

         gets(str);

         int len=strlen(str);

         str1[][]=;

         str1[][]=;

         for(i=;i<len;i++)

         {

             int c=,k;

             for(k=;k<maxn;k++)

             {

                 int s=str1[i-][k]+str1[i-][k]+c;

                 str1[i][k]=s%;

                 c=s/;

             }

             while(c)

             {

                 str1[i][k++]=c%;

                 c/=;

             }

         }

         for(i=;i>=;i--)

             if(str1[len-][i])

                 break;

         for(j=i;j>=;j--)

             printf("%d",str1[len-][j]);

             printf("\n");

     }

     return ;

 }

 #include<stdio.h>

 #include<string.h>

 #define N 210

  int f[][N];

  void init()

  {

      int i, j;

      f[][] = ;

        f[][] = ;

        for(i = ; i <= ; i++)

         for(j = ; j <= ; j++)

        {

            f[i][j] += f[i-][j] + f[i-][j];

            if(f[i][j] >= )

            {

                f[i][j] -= ;

                f[i][j+]++;

            }

        }

  }

 int main()

 {

    int i, j, t;

    char s[N];

    scanf("%d", &t);

    init();

    while(t--)

    {

        scanf("%s", s);

        int n = strlen(s);

         int k = ;

         for (; f[n][k] ==  ; k--);

         for (; k >=  ; k--)

             printf ("%d",f[n][k]);

             printf("\n");

    }

    return ;

 }