codeforces-scrape

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

319A.md (1817B)


      1 Source: https://codeforces.com/problemset/problem/319/A
      2 
      3 A. Malek Dance Club
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 As a tradition, every year before IOI all the members of Natalia Fan Club are invited to Malek Dance Club to have a fun night together. Malek Dance Club has 2*n* members and coincidentally Natalia Fan Club also has 2*n* members. Each member of MDC is assigned a unique id *i* from 0 to 2*n* - 1. The same holds for each member of NFC.
     22 
     23 One of the parts of this tradition is one by one dance, where each member of MDC dances with a member of NFC. A dance pair is a pair of numbers (*a*, *b*) such that member *a* from MDC dances with member *b* from NFC.
     24 
     25 The complexity of a pairs' assignment is the number of pairs of dancing pairs (*a*, *b*) and (*c*, *d*) such that *a* < *c* and *b* > *d*.
     26 
     27 You are given a binary number of length *n* named *x*. We know that member *i* from MDC dances with member ![](https://espresso.codeforces.com/064f62f758022f9f352d238ee5ed93ec9a92138b.png) from NFC. Your task is to calculate the complexity of this assignment modulo 1000000007 (109 + 7).
     28 
     29 Expression ![](https://espresso.codeforces.com/b364f2e04c665b78b924ec10666327a4ef4635bc.png) denotes applying «XOR» to numbers *x* and *y*. This operation exists in all modern programming languages, for example, in C++ and Java it denotes as «^», in Pascal — «xor».
     30 
     31 Input
     32 
     33 The first line of input contains a binary number *x* of lenght *n*, (1 ≤ *n* ≤ 100).
     34 
     35 This number may contain leading zeros.
     36 
     37 Output
     38 
     39 Print the complexity of the given dance assignent modulo 1000000007 (109 + 7).
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 11
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 6
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 01
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1
     77 ```