小苯有一个长度为 的数组 ，其中第 个数字的值为 。 现在小苯会对 施加 个魔法，具体的，第 个魔法表示为 ，施法后会使得 这一段的数字都加上 。 但身为见习魔法师的小苯法力并不稳定，具体来说这 个魔法并不会全部施法成功，而是会随机且等概的失效一个魔法，只有 个魔法施法成功，他想知道这样的情况下，数组 最大值的期望是多少，请你帮他算一算吧。

输入描述:

每个测试文件内都包含多组测试数据。第一行一个正整数 ，表示测试数据的组数。接下来对于每组测试数据，输入包含  行。第一行两个整数 ，表示数组  的长度，以及小苯的施法次数。第二行  个整数 ，表示数组 。接下来 行，每行三个正整数 ，描述每一个魔法。（保证所有测试数据中  的总和都不超过 。）

输出描述:

对于每个测试数据，输出一行一个整数表示数组的最大值对 取模的值。（分数取模的定义：可以证明，这个期望一定是一个有理数，如果写成  的形式，你输出的  需要保证  对  取模恰好等于 。）Python选手建议通过Pypy、Pypy3语言进行提交。