#P3542. History of Football

    ID: 2552 远端评测题 8000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Northeastern Europe 2007, Northern Subregion

History of Football

Description

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:

Possible table number 1TeamABCPointsA-303B0-33C30-3Possible table number 2TeamABCPointsA-033B3-03C03-3

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

Input

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

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.

3
3
3
3
2

Source

Northeastern Europe 2007, Northern Subregion