香霖堂出售 种道具，用 编号， 号道具的售价为 。
香霖堂推出了 项活动，每项活动可以用三个数 表示，内容为：
现在你没有香霖堂出售的任何一种道具，请你对于任意的 （）计算，想使用不超过 元，购买任意一件道具并将其兑换成 号道具，一共有多少种不同的方案。
两种取得道具的方案不同，等价于以下至少一项满足：
答案可能很大，对 取模。
第一行有三个整数 ，表示香霖堂出售的道具数、香霖堂的活动数和你的钱数。
第二行有 个整数 ，表示 件道具的售价。
接下来有 行，每行用 三个整数描述一项活动，表示你可以在香霖堂支付 元，用 号道具兑换 号道具。
个整数。第 个整数表示使用不超过 元购买任意一件道具并将其兑换成 号道具的方案数，对 取模。
4 2 4 1 2 3 4 1 4 4 2 4 2
1 1 1 2
样例解释
这里以获得 号物品的方案数为例。获得 号物品的方案数为 。
第一种方案：直接购买 号物品，花费 元。
第二种方案：购买 号物品并兑换成 号物品，花费 元。
数据范围
对于 的数据，，。
对于 的数据，。
对于另外 的数据，保证任何一个道具不能经过若干次交换得到其本身。
对于所有数据，，，。
对于一项活动，，，。
