seuOJ431 - 三色问题

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：2022

题目描述

给你一个长度为$n$的正整数序列$a$，把每个数字涂成红、绿或蓝，问有多少种上色方案使得三种颜色的数字和可以构成三角形的三边长。

输入格式

第一行一个正整数$n$。 接下来$n$行，表示$a$序列。

输出格式

输出一个数字，表示方案数对998244353取模的值。

样例

输入样例1

4
1 1 1 2

输出样例1

18

输入样例2

6
1 3 2 3 5 2

输出样例2

150

输入样例3

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

输出样例3

563038556

数据范围与提示

$1\leq n,a_i\leq 300$ 。

请注意此题较为特殊的空间限制。