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

output

input

V_V

output

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 ;

}

巴特西

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

最新文章

热门文章