Just a few numbers P52945

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 + 10⁸)! mod(10⁹ + 123).

Input

Input consists of several cases, each with just the input for problem 1: a number n between 1 and 10⁴, 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.