题目描述

泽拉斯诺坦纳多是极北之地的一座古城，每到暖季，都会有一大批探索者来到这里，探索地底深处未知的宝藏。

@zls_XICK 是一名初来乍到的探索者，意外之下发现了一个塌陷的洞穴，洞穴里整齐地插着火把，木柄略有腐朽，深处是一个宽阔的空间。

空间中心摆着 $n$ 个玄武岩和一个宝箱，每个玄武岩上分别刻着一位阿拉伯数字 $a_1$∼$a_n$，这些数字都是一位正整数，前辈留给他的皮质笔记上面有 $m$ 条咒语，可以用来改变这些数字，这 $m$ 条咒语无需按顺序念出。

很显然，@zls_XICK 需要用这些咒语来改变玄武岩上的数字以打开宝箱，但是他没有什么探索经验，不知道怎样才能最快找到正确的数字组合，所以他决定暴力枚举尝试每种组合。

这 $m$ 条咒语分别由 $type_i,x_i,y_i$ 三个要素组成，其中 $type_i$ 包含 $1$ 和 $0$ 两种，其规则如下：

• 若 $type_i$ 为 $1$，表示此咒语可以把数字为 $x_i$ 的任意一块玄武岩数字变为 $y_i$。

• 若 $type_i$ 为 $0$，表示此咒语可以把第 $x_i$ 块玄武岩数字变为 $y_i$。

• $type_i$ 为 $1$ 的咒语可以念无数次，$type_i$ 为 $0$ 的咒语至多且必须念一次。

现在 @zls_XICK 需要预先知道最后的数字组合可以有多少种以防止念咒语累死，当然，这里的组合也包括原来的组合，也就是还没念任何咒语时的组合。

输入格式

输入共 $m + 2$ 行。

第一行 $2$ 个整数 $n$ 和 $m$，含义如题意。

第二行 $n$ 个整数 $a_1$∼$a_n$，表示玄武岩上原来的数字。

随后 $m$ 行，每行三个整数 $type_i,x_i,y_i$，表示第 $i$ 条咒语的三个要素。

输出格式

一行一个整数，表示玄武岩上的数字的组合有几种。

3 3
4 5 6
1 5 6
0 1 5
1 6 3

19

数据规模与约定

对于 $20 \%$ 的数据满足 $type_i = 0$。

对于 $100 \%$ 的数据满足 $1 \le n \le 150$，$1 \le m \le 10^6$，$1 \le a_i \le 9$，$type \in \left[ 0, 1 \right]$。