{"raw_statement":[{"iden":"statement","content":"ZHY 的记忆中有一个 $k$ 行 $n$ 列的 01 矩阵 $A$，满足下列条件：\n\n- 每一列都至多有一个 $1$。\n- 每行相邻的两个 $1$ 所在的两列夹出的 $k$ 行的矩形（包括这两列）内至少有三个 $1$。\n\n突然，ZHY 想起来了矩阵中 $x$ 个位置的值。请你计算有多少种填充 $A$ 的剩余位置的方案，使得 $A$ 满足条件。\n\n----\n\n形式化的讲，设 $A$ 第 $i$ 行第 $j$ 列的数为 $A_{i,j}$，则 $A$ 满足下列条件：\n\n- 对于 $\\forall i \\in [1,k],\\kern{2pt}j \\in [1,n]$，$A_{i,j} \\in \\{0,1\\}$。\n\n- 对于 $\\forall i \\in [1,n]$，$\\displaystyle\\sum_{j=1}^{k} A_{j,i}\\le 1$。\n\n- 对于 $\\forall i,j \\in [1,n],\\kern{2pt}p \\in [1,k]$ 且 $j>i$，若有 $A_{p,i}=A_{p,j}=1,\\displaystyle \\sum_{x=i}^{j}A_{p,x}=2$，则有 $\\Big(\\displaystyle \\sum_{x=1}^{k} \\sum_{y=i}^{j} A_{x,y}\\Big) \\ge 3$。\n\n- 对于 $\\forall i\\in[1,x]$，有 $A_{a_{i},b_{i}}=c_{i}$。\n\n由于答案可能很大，你只需告诉 ZHY 答案对 $10^{9}+7$ 取模的结果。定义两个矩阵 $A,A'$ 不同，当且仅当存在 $i\\in[1,k]$，$j\\in[1,n]$ 满足 $A_{i,j}\\ne A'_{i,j}$。"},{"iden":"input","content":"第一行三个整数，表示 $n,k,x$。\n\n接下来 $x$ 行，每行三个整数 $a_{i},b_{i},c_{i}$。"},{"iden":"output","content":"一行一个整数，表示答案。"},{"iden":"note","content":"**样例解释**\n\n满足条件的矩阵只有以下 $2$ 种：\n\n$$\n\\begin{Bmatrix}\n1&0&0\\\\\n0&0&0\n\\end{Bmatrix}\n$$\n\n$$\n\\begin{Bmatrix}\n1&0&0\\\\\n0&0&1\n\\end{Bmatrix}\n$$\n\n----\n\n\n**本题采用捆绑测试。**\n\n| $\\mathrm{Subtask} \\kern{2pt} \\mathrm{id}$ | $n$ | $x$ | 特殊性质 | 分值 |\n| :-----: | :-----: | :-----: | :-----: | :-----: |\n| $0$ | $\\le 8$ | $\\le 8$ | $k=2$ | $12$ |\n| $1$ | $\\le 2 \\times 10^{5}$ | $\\le 2\\times 10^{5}$ | 无 | $26$ |\n| $2$ | $\\le 10^{9}$ | $=0$ | 无 | $23$ |\n| $3$ | $\\le 10^{9}$ | $\\le 2\\times 10^{5}$ | $c_{i}=1$ | $15$ |\n| $4$ | $\\le 10^{9}$ | $\\le 2\\times 10^{5}$ | 无 | $24$ |\n\n对于所有数据，$1 \\le n \\le 10^{9}$，$0 \\le x \\le 2\\times 10^{5}$，$2\\le k \\le 100$。$1 \\le a_{i} \\le k$，$1 \\le b_{i} \\le n$，$c_{i} \\in \\{0,1\\}$。保证不存在一对 $i,j \\in [1,x],\\kern{2pt}i\\neq j$，满足 $a_{i}=a_{j},\\kern{2pt}b_{i}=b_{j}$。"}],"translated_statement":null,"sample_group":[["3 2 2\n1 1 1\n2 2 0\n","2\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}