Vanya and Label

Description

While walking down the street Vanya saw a label "Hide&Seek". Because he is a programmer, he used & as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string s and wants to know the number of pairs of words of length |s| (length of s), such that their bitwise AND is equal to s. As this number can be large, output it modulo 109 + 7.

To represent the string as a number in numeral system with base 64 Vanya uses the following rules:

  • digits from '0' to '9' correspond to integers from 0 to 9;
  • letters from 'A' to 'Z' correspond to integers from 10 to 35;
  • letters from 'a' to 'z' correspond to integers from 36 to 61;
  • letter '-' correspond to integer 62;
  • letter '_' correspond to integer 63.

Input

The only line of the input contains a single word s (1 ≤ |s| ≤ 100 000), consisting of digits, lowercase and uppercase English letters, characters '-' and '_'.

Output

Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 109 + 7.

Sample Input

Input
z
Output
3
Input
V_V
Output
9
Input
Codeforces
Output
130653412


#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100000+10;
const int modul=1000000000+7;

char st[maxn];

int pan(int n)
{
	int i;
	int num=0;
	for(i=0;i<=5;i++)
	{
		int x=n>>i;
		if(!(x&1))
			num++;
	}
	return num;
}

int tra(char a)
{
	int n;
	if(a>='0'&&a<='9')
	{
		n=a-'0';
	}
	else if(a>='A'&&a<='Z')
	{
		n=a-'A'+10;
	}
	else if(a>='a'&&a<='z')
	{
		n=a-'a'+36;
	}
	else if(a=='-')
	{
		n=62;
	}
	else if(a=='_')
	{
		n=63;
	}
	return pan(n);
}

int main()
{
	int ans=0;
	scanf("%s",&st);
	int n=strlen(st);
	int i;
	__int64 j=1;
	for(i=0;i<n;i++)
	{
		ans+=tra(st[i]);
	}
	for(i=0;i<ans;i++)
	{
		j=(j*3)%(modul);
	}
	printf("%I64d\n",j);
	return 0;
}


版权声明：本文为qq_35109299原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。