Description

提示信息： 树形结构中的一条完整路径定义为从根节点到任意一个叶节点所经过边的集合。 题目描述： 给定包含n个节点的二叉树，节点编号从1到n，其中根节点为1号，请判断二叉树中存在多少条完整路径满足该路径上的所有节点值之和能够被3整除。

时间限制：1s 内存限制：256MB

Format

Input

第一行包含一个整数n，表示二叉树的节点数量； 第二行包含n个整数v1，v2，v3，..., vn,分别表示1号到n号节点的值，整数之间以一个空格隔开； 接下来n行，每行包含3个整数x，y，z，分别表示二叉树中每个节点编号，及其对应的左子节点和右子节点的编号（0表示对应子节点为空），整数之间以一个空格隔开。

数据范围： 测试点1～10:1<=n<=1000,1<=x,y,z<=n,1<=vi<=5000

Output

一个整数，表示二叉树中存在多少完整路径满足路径上的所有节点值之和能够被3整除。

Samples

6
50 32 78 47 54 80
1 2 3
3 5 6
2 0 4
4 0 0
5 0 0
6 0 0

1

7
12 7 29 15 36 18 52
1 4 5
4 2 0
2 0 3
5 7 6
3 0 0
6 0 0
7 0 0

2