喜羊羊发现了一个古战场，马上报告了村长。村长查阅了9999本历届村长手记，告诉喜羊羊，那个古战场有大的机遇，但同时也有很大风险。喜羊羊决定带一些喜欢探险的羊去古战场。不过打开古战场的密码很复杂，你能帮帮喜羊羊吗？
要破解密码，首先需要知道战场外的一个“六门锁”。所谓六门锁就是由2行。3列或更多列组成的一个长方形格子,其中任何连续的3列有6个格子，这6个格子的和等于K。初始时一些格子是空的，还有一些格子上有一个一位数(这个数是不能动的），不同的格子数字可能不同，你需要把这些空的位置填上0-9这些数。打开战场的密码就是总共有多少种不同的填法。

第一行输入3个整数，n(3<=n<=100000),k(0<=k<=100),m(0<=m<=200000.n代表总共有多少列，k是六门锁的和，m指的初始时有m个数已经填上去了。
后面是m行，每行由3个整数组成，c(0<=c<=n-1),r(0<=r<=1)和V(0<=v<=9),代表c行r列的填上的数值时v

输出总共有多少种填法，如果这个数值很大，请先对1000000007取模。