《National Gentlemen and Ladies Beer Magazine》是一本时尚杂志，每月举办针对年轻 IT 专家的竞赛，而这些专家恰好也是该杂志的主要订阅者。竞赛基于一种名为“Sixpack”的谜题，印在杂志的第一页，背景是时尚的啤酒泡沫。该谜题由一个两行、三列或更多列的矩形网格组成。网格中的一些单元格是空的，一些包含单个十进制数字，不同的单元格可能包含不同的数字。在极端情况下，网格可能为空，也可能被完全填满。网格中任意三列连续的列被称为一个“sixpack”，这也是该谜题名称的由来。

网格还附带另一个整数 $K$，它是谜题不可或缺的一部分。

读者的任务是用单个数字填充网格中的每个空单元格，使得每个 sixpack 中所有数值之和等于 $K$。不同的单元格可以包含不同的数字。接下来，读者将他或她的谜题解发送给杂志的顾问委员会。委员会会记录他们收到的所有解。当读者的解与委员会之前收到的某个解相同时，该读者不会赢得任何奖品。当读者的解与委员会迄今为止收到的所有解都不同时，读者将赢得一箱优质品牌的真啤酒 sixpack。奖品中 sixpack 的数量等于在委员会收到该读者的解之后，委员会所拥有的不同谜题解的总数。

如果两个解在网格中至少有一个位置的单元格内容不同，则认为它们是不同的。

每位读者最多只能提交一个解。同一读者提交的任何额外解都将被驳回。委员会秘书保证委员会永远不会在同一时刻收到两个或多个解。

给定一个特定的 Sixpack 谜题，计算杂志读者在相应竞赛中可能赢得的啤酒 sixpack 的最大数量。该杂志非常受欢迎，因此可以确定杂志读者的数量多于谜题唯一解的数量。

输入格式

输入描述了一个 Sixpack 谜题。第一行包含三个整数 $N$ ($3 \le N \le 10^5$)、$K$ ($0 \le K \le 100$) 和 $M$ ($0 \le M \le 2 \cdot 10^5$)。$N$ 是网格的列数，$K$ 指定了每个 sixpack 的规定和，$M$ 是网格中预定义值的数量。接下来的 $M$ 行，每行包含三个整数 $C$ ($0 \le C \le N - 1$)、$R$ ($0 \le R \le 1$) 和 $V$ ($0 \le V \le 9$)。$C$ 和 $R$ 指定了网格中单元格的列和行，$V$ 是该单元格的预定义值。每个单元格的值在输入中最多被指定一次。

输出格式

输出杂志读者可能赢得的啤酒 sixpack 的最大数量。请将此数字对 $1\,000\,000\,007$ 取模。

样例

输入 1

3 2 0

输出 1

21

输入 2

5 17 2
0 1 5
4 0 2

输出 2

11580