C. mathematican 的二进制

有一个长度很大的二进制串，初始时它的每一位都为 0。现在有 个操作，其中第 个操作是将这个二进制串的数值加上 ，或者说，给第 位加上 并进位，我们称每次操作的代价是这次操作改变的位的数量。例如，当前的二进制串是 时，如果给它加上 ，串就变成了 ，其中从低到高第 位发生了改变，那么这次操作代价为 。

我们以一定概率执行这些操作：第 个操作有 的概率执行，否则不执行。请求出所有执行的操作的代价和的期望。

你只需要求出期望改变的位数在模 意义下的值。具体来说，如果你算出来的期望，其中 互质，那么你只要输出 ，其中 表示 在 意义下的逆元。

注意：执行完操作后，该串去除前导 后的长度可能大于 。

第一行两个用空格分隔的正整数 ，分别表示 的范围和操作数，如上文所述。

接下来 行，每行三个正整数 ，其中 。

仅一行，表示答案。

样例输入 1

4 4
0 1 2
0 1 2
0 1 2
0 1 2

样例输出 1

187170819

样例输入 2

233 6
1 166 233
2 233 666
3 166 266
4 233 266
5 233 666
6 166 233

样例输出 2

56615945

样例 3

见附加文件。

对于所有数据，。