Just a few numbers P52945


Statement
 

pdf   zip

thehtml

Evil professor Oak has captured Albert, Enric and Eric in his dungeon, and forces them to solve problems. He promised to free them, but only when all of them have solutions. They need to solve the problems one after the other, using the output of the previous problem for the input of the next one. Go, fellow contestant, help your friends!

  1. Albert’s riddle: Prof. Oak wants to figure out which day of the month a programming contest will take place. Given n votes, determine which number is the most popular.
  2. Enric’s puzzle: Using Albert’s output A, calculate how many sequences of 0s and 1s of length A have at least two consecutive 1s.
  3. Eric’s conundrum: Using Enric’s output E, compute (E + 108)! mod(109 + 123).

Input

Input consists of several cases, each with just the input for problem 1: a number n between 1 and 104, followed by n natural numbers between 1 and 31. Assume that the winning date is always a clear winner, without ties.

Output

For every case, print only the solution of the third problem.

Public test cases

  • Input

    9  2 29 18 18 29 2 18 2 18
1  7
2  1 1

    Output

    75668734
145960886
701242570
    • Information
    Author
    Enric Cusell, Albert Martinez and Eric Milesi
    Language
    English
    Official solutions
    C++
    User solutions
    C++