URI Online Judge | 3138

Tobias Birthday

By Roger Eliodoro Condras, UFSC-ARA BR Brazil

Timelimit: 1

Today is Tobias birthday (congratulations!) and as we are currently going through a moment of social isolation, he decided to have an online party in order to celebrate the date with his friends.

Like all good programmers, Tobias is very fond of balloons. And of course it was not on their birthday that they would be left out. He decided to hang some on his wall in order to leave his room decorated for the virtual party later.

Tobias had balloons of various colors kept at home and started to hang them next to each other. While hanging he was wondering if that order was good, or if he should put them in some different order and how many ways he could change those balloons to get a different sequence.

Given the list of how many balloons of each color Tobias found at home, can you help him know what number of different strings he can get by rearranging the position of his balloons?

Note that changing two balloons of the same color in place does not generate a new sequence and it is guaranteed that Tobias will use all the balloons he found and that this number does not exceed 20.

Input

An integer N (0 \(\leq\) N \(\leq\) 20). Then there will be N lines, each with a string S (1 \(\leq\) |S\(\leq\) 15) and an integer B (1 \(\leq\) B \(\leq\) 20) separated by a space. The name of a color and the number of balloons respectively.

The string S is formed only by lowercase letters of the english alphabet without spaces and it is guaranteed that the sum of the total number of balloons does not exceed 20.

Output

An integer, the total number of distinct strings that Tobias can obtain by changing the order balloons.

As today is his birthday, print "Feliz aniversario Tobias!" (without quotes) one line before printing the answer. :)

Input Sample Output Sample

3
vermelho 2
azul 2
verde 1

Feliz aniversario Tobias!
30