← 返回题目列表

AtCoder · tenka1_2019_d

D. 三种颜色

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

你被给予 N 整数。 i第一个整数是 a_i。 求模数 998244353,将每个整数绘制为红色、绿色或蓝色以满足以下条件的方法:

  • 让 R, G 和 B 分别是红色、绿色和蓝色的整数之和。存在一个面积为正的三角形,其边长为 R, G 和 B.

约束

  • 3 \leq N \leq 300
  • 1 \leq a_i \leq 300(1\leq i\leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
a_1
:
a_N

输出

打印数字,模数 998244353,将每个整数涂成红色、绿色或蓝色以满足条件的方法。


示例输入 1

4
1
1
1
2

示例输出 1

18

我们只能绘制整数,以便三角形的边长为 1, 2 和 2,并且有 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