codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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*