12720

//1101110 =110
//
//1101010
//1101110
//1101010

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

#define MOD 1000000007

using namespace std;

unsigned long long x[100001];
unsigned long long y;


int main()
{
	int t,l,m,kase=0;
	int a,b;
	string str,s;

	x[0]=1;
	x[1]=2;

	for(int i=2;i<100001;i++)
		x[i]=(x[i-1]*2)%MOD;

	cin>>t;

	while(t--)
	{
		cin>>str;
		y=0;
		s="";
		kase++;

		if(str.size()%2==1)
		{
			a=str.size()/2;
			b=a;
		}
		else
		{
			b=str.size()/2;
			a=b-1;
		}

		for(int i=0;i<str.size();i++)
		{
			if(s.size()==str.size())
			break;
			if(a==b)
			{
				s.append(1u,str[a]);
				l=str.size()-s.size();
				y+=((x[l]*(str[a]-'0'))%MOD);
				y%=MOD;
				a=a-1;
				b=b+1;
			}
			else
			{
				if(str[a]>=str[b])
				{
					s.append(1u,str[a]);
					l=str.size()-s.size();
					y+=((x[l]*(str[a]-'0'))%MOD);
					y%=MOD;

					s.append(1u,str[b]);
					l=str.size()-s.size();
					y+=((x[l]*(str[b]-'0'))%MOD);
					y%=MOD;
					a--;
					b++;
				}
				else
				{
					s.append(1u,str[b]);
					l=str.size()-s.size();
					y+=((x[l]*(str[b]-'0'))%MOD);
					y%=MOD;

					s.append(1u,str[a]);
					l=str.size()-s.size();
					y+=((x[l]*(str[a]-'0'))%MOD);
					y%=MOD;
					b++;
					a--;
				}
			}
		}
		cout<<"Case #"<<kase<<": ";
		cout<<y<<"\n";
	}
	return 0;
}