暂无测试数据。

Aero 国的生物学家 Areo 最近发现了一种神奇的生物。这种生物的寿命与繁殖均由概率决定。具体地，共有 $m$ 种情况，第 $i$ 种情况发生的概率为 $p_i$，此时一个生物的寿命恰好为 $t_i$ 天，在它死亡的瞬间会诞生 $s_i$ 个同样的生物（注意 $s_i$ 可以等于 $0$）。这种生物的死亡只会发生在每天晚上 $24:00$ ，也即次日凌晨 $0:00$，所有此时应当死亡的生物会同时死亡，随后应当诞生的生物会同时诞生。不同的生物的概率是彼此独立的。现在，Aero 国内共有 $n$ 个这样的生物，那么 $l$ 天之后（即第 $l+1$ 天 $0:00$，应当死亡的生物全部死亡后），这种生物没有灭绝（只要仍有未死亡的或有新诞生的都算没有灭绝）的概率是多少呢？

输入格式

第一行，三个正整数 $n,l,m$。

接下来 $m$ 行，每行三个整数 $q_i,t_i,s_i$。你需要自己计算 $p_i=\dfrac{q_i}{\sum_{j=1}^mq_j}$。出现重复的情况是可能的。

输出格式

答案可以表示成既约分数 $a/b$ 的形式（保证 $b$ 在模 $1000000007$ 下存在逆元），你只需输出 $a\cdot b^{-1}\bmod 1000000007$ 即可。

提示：对于质数 $p$，$[1,p)$ 中的整数 $x$ 在模 $p$ 意义下的逆元为 $x^{-1}\equiv x^{p-2}\pmod p$。

数据规模与约定

对于前 $20\%$ 的数据，$n,l,m\le 5$。

对于前 $40\%$ 的数据，$n,l,m\le50$。

对于前 $60\%$ 的数据，$n\le10^5$，$l,m\le2000$。

对于 100% 的数据，$1\le n\le10^9$，$1\le l,m\le 2000$，$1\le q_i\le100$，$1\le t_i\le3000$，$0\le s_i\le n$。

1 3 2
1 2 0
2 1 2

925925933