Description

目描述
俄罗斯世界杯比赛举办得如火如荼，我们知道在小组赛中，一组有4只球队，每两支球队恰好比赛一场，平局时各得1分，而胜负是胜者得3分，负者0分。
假设四支球队得分分别为6，6，3，3，则他们之间的比赛情况可能如下：

还可能是其他情况，现在假设一个小组有n只队伍，给出n只队伍的最终得分，统计有多少种可能的不同的比赛胜负情况。

Format

Input

第一行包含一个正整数n(n<=8)，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。

Output

输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。

Sample 1

Input

4
6 6 3 3

Output

4

Limitation

1s, 256MiB for each test case.
1≤n≤8