C1428 [CQOI2009]循环赛

内存限制:256 MB 时间限制:1000 ms

题目描述

$n$ 支队伍打比赛,每两支队伍恰好比赛一场。平局时各得 $1$ 分,而有胜负时胜者 $3$ 分,负者 $0$ 分。

假设三支队伍得分分别为 $3$,$3$,$3$,则可能有两种情况:

$\begin{array}{|c|c|c|c|c|}\hline 队伍 & A & B & C & 得分 \\ \hline A & - & 3 & 0 & 3 \\ \hline B & 0 & - & 3 & 3 \\ \hline C & 3 & 0 & - & 3 \\ \hline \end{array}$

$\begin{array}{|c|c|c|c|c|}\hline 队伍 & A & B & C & 得分 \\ \hline A & - & 0 & 3 & 3 \\ \hline B & 3 & - & 0 & 3 \\ \hline C & 0 & 3 & - & 3 \\ \hline \end{array}$

给出 $n$ 支队伍的最终得分(即所有比赛均已结束),统计有多少种可能的分数表。

输入格式

第一行包含一个正整数 $n$,队伍的个数。第二行包含 $n$ 个非负整数,即每支队伍的得分。

输出

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

样例

样例输入 1

6 5 6 7 7 8 8

样例输出 1

121

提示

$N \le 8$