codeforces-scrape

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

1245C.md (2677B)


      1 Source: https://codeforces.com/problemset/problem/1245/C
      2 
      3 C. Constanze's Machine
      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 Constanze is the smartest girl in her village but she has bad eyesight.
     22 
     23 One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce 'c', 'o', 'd', and 'e' in that order, then the machine will inscribe "code" onto the paper. Thanks to this machine, she can finally write messages without using her glasses.
     24 
     25 However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce 'w', it will inscribe "uu" instead of "w", and if you pronounce 'm', it will inscribe "nn" instead of "m"! Since Constanze had bad eyesight, she was not able to realize what Akko did.
     26 
     27 The rest of the letters behave the same as before: if you pronounce any letter besides 'w' and 'm', the machine will just inscribe it onto a piece of paper.
     28 
     29 The next day, I received a letter in my mailbox. I can't understand it so I think it's either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze's machine would have turned into the message I got and see if anything makes sense.
     30 
     31 But I need to know how much paper I will need, and that's why I'm asking you for help. Tell me the number of strings that Constanze's machine would've turned into the message I got.
     32 
     33 But since this number can be quite large, tell me instead its remainder when divided by $10^9+7$.
     34 
     35 If there are no strings that Constanze's machine would've turned into the message I got, then print $0$.
     36 
     37 Input
     38 
     39 Input consists of a single line containing a string $s$ ($1 \leq |s| \leq 10^5$) — the received message. $s$ contains only lowercase Latin letters.
     40 
     41 Output
     42 
     43 Print a single integer — the number of strings that Constanze's machine would've turned into the message $s$, modulo $10^9+7$.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 ouuokarinn
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 4
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 banana
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 nnn
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 3
     81 ```
     82 
     83 Input
     84 
     85 ```
     86 amanda
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 0
     93 ```
     94 
     95 Note
     96 
     97 For the first example, the candidate strings are the following: "ouuokarinn", "ouuokarim", "owokarim", and "owokarinn".
     98 
     99 For the second example, there is only one: "banana".
    100 
    101 For the third example, the candidate strings are the following: "nm", "mn" and "nnn".
    102 
    103 For the last example, there are no candidate strings that the machine can turn into "amanda", since the machine won't inscribe 'm'.