#P6929. 机器人
机器人
机器人
题目描述
有一个机器人,这个机器人有一段长度为的程序,程序的每一位是四个字母之一,表示这个机器人向下/左/右/上移动一步。
这个机器人会以 为起点,以为一个时间周期,不断重复这个程序。
现在你知道的是在某些时刻机器人所在的坐标,你要求出有多少种合法的程序,输出答案对 取模后的结果。
输入格式
第一行两个整数 和,表示你知道的坐标个数和程序长度。
接下来行每行三个整数 和,表示在 时刻机器人的坐标是 。
输出格式
输出一行一个整数表示合法的程序数,输出答案对 取模后的结果。
样例输入1
3 5
1 1 0
2 1 -1
3 0 -1
样例输出1
16
样例 2
见下发文件 robot2.in/out。
数据范围和约定
对于 % 的测试数据,满足。 对于 % 的测试数据,满足。 对于 % 的测试数据,满足。
对于 % 的测试数据,满足$1\le n\le 200000,1\le l\le 2000000,1\le t\le 10^{18}$。