#P6929. 机器人

    ID: 6760 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-模拟与实现技巧坐标变换枚举与搜索暴力枚举构造与建模差分转化组合数学乘法原理阶乘逆元预处理数论向下取整与向上取整CF2500

机器人

机器人

题目描述

有一个机器人,这个机器人有一段长度为ll的程序,程序的每一位是D,L,R,UD,L,R,U四个字母之一,表示这个机器人向下/左/右/上移动一步。

这个机器人会以 (0,0)(0,0) 为起点,以ll为一个时间周期,不断重复这个程序。

现在你知道的是在某些时刻机器人所在的坐标,你要求出有多少种合法的程序,输出答案对 109+710^{9}+7取模后的结果。

输入格式

第一行两个整数nn 和ll,表示你知道的坐标个数和程序长度。

接下来nn行每行三个整数t,xt,x 和yy,表示在tt 时刻机器人的坐标是 (x,y)(x,y)。

输出格式

输出一行一个整数表示合法的程序数,输出答案对 109+710^{9}+7取模后的结果。

样例输入1

3 5
1 1 0
2 1 -1
3 0 -1

样例输出1

16

样例 2

见下发文件 robot2.in/out。

数据范围和约定

对于 1010% 的测试数据,满足n,l≤10n,l\le 10。 对于 3030% 的测试数据,满足n,l≤200n,l\le 200。 对于 5050% 的测试数据,满足n,l≤5000n,l\le 5000。

对于 100100% 的测试数据,满足$1\le n\le 200000,1\le l\le 2000000,1\le t\le 10^{18}$。