Henry is a historian. He specializes in the history of sports, especially football. Whenever he sees a table of a football tournament, he saves it into his database.

Recently he ran across a web-site with standings of a small tournament. Unfortunately for him, the results of the games were lost, and the only available information was the amount of points gained by each team.

Disappointed by that, he decides to have some mathematical fun and to calculate in how many different ways the games of the championship could have ended. He doesn’t care about the scores of the games, he only cares about the winners.

In that tournament the following rules were applied:

• Each team plays against each other team exactly once.
• In case of a tie each team gains 1 point.
• In other case the winner gains 3 points and the loser gains 0 points.

For example, if Henry knows that each of 3 teams had got 3 points by the end of the tournament, the answer to his question is that there are two possible tournament tables:

Help Henry calculate the number of different possible tournament tables (without consideration of the scores of the games).

Input file contains integer n, the number of teams in the championship (2 ≤ n ≤ 8). The following n lines contain one integer number each — points gained by the teams.

Output one integer number — the number of possible tournament tables with given total points. It is guaranteed that there is at least one such tournament table.