codeforces 677C C. Vanya and Label(组合数学+快速幂)

题目链接：

C. Vanya and Label

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Examples

input

z

output

3

input

V_V

output

9

input

Codeforces

output

130653412

题意：

每一位用这些字符来代替,问有多少对与s相同长度的字符串的&运算之后等于s;

思路：

把这些字符转化成数字后变成2进制,看有多少个0,如果有n个0,那么就是3的n次方;
因为每一个为0的位置上可以有0&1,1&0,0&0,这3种情况,最后结果就是3的n次方了,快速幂;

AC代码：

#include <bits/stdc++.h>
/*#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
*/
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
    for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
    F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
    if(!p) { puts(""); return; }
    while(p) stk[++ tp] = p%, p/=;
    while(tp) putchar(stk[tp--] + '');
    putchar('\n');
}

const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e10;
const int N=1e5+;
char s[N];
int check(int x)
{
    if(s[x]>=''&&s[x]<='')return s[x]-'';
    else if(s[x]>='a'&&s[x]<='z')return s[x]-'a'+;
    else if(s[x]>='A'&&s[x]<='Z')return s[x]-'A'+;
    else if(s[x]=='-')return ;
    else if(s[x]=='_')return ;
}
int fun(int x)
{
    int num=;
    int cnt=;
    while(cnt--)
    {
        if(x%==)num++;
        x=(x>>);
    }
    return num;
}
LL fastpow(int y)
{
    LL ans=,base=;
    while(y)
    {
        if(y&)
        {
            ans=ans*base;
            ans%=mod;
        }
        base=base*base;
        base%=mod;
        y=(y>>);
    }
    return ans;
}

int main()
{
    scanf("%s",s);
    int len=strlen(s);
    int sum=;
    for(int i=;i<len;i++)
    {
        int x=check(i);
        sum=sum+fun(x);
    }
    print(fastpow(sum));
    return ;
}