677C.md (1742B)
1 Source: https://codeforces.com/problemset/problem/677/C 2 3 C. Vanya and Label 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 To represent the string as a number in numeral system with base 64 Vanya uses the following rules: 24 25 * digits from '0' to '9' correspond to integers from 0 to 9; 26 * letters from 'A' to 'Z' correspond to integers from 10 to 35; 27 * letters from 'a' to 'z' correspond to integers from 36 to 61; 28 * letter '-' correspond to integer 62; 29 * letter '_' correspond to integer 63. 30 31 Input 32 33 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 '_'. 34 35 Output 36 37 Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string *s* modulo 109 + 7. 38 39 Examples 40 41 Input 42 43 ``` 44 z 45 ``` 46 47 Output 48 49 ``` 50 3 51 ``` 52 53 Input 54 55 ``` 56 V_V 57 ``` 58 59 Output 60 61 ``` 62 9 63 ``` 64 65 Input 66 67 ``` 68 Codeforces 69 ``` 70 71 Output 72 73 ``` 74 130653412 75 ``` 76 77 Note 78 79 For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia. 80 81 In the first sample, there are 3 possible solutions: 82 83 1. *z*&_ = 61&63 = 61 = *z* 84 2. _&*z* = 63&61 = 61 = *z* 85 3. *z*&*z* = 61&61 = 61 = *z*