v_calc
题号：NC304229
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定 n 个限制条件 (A_i, L_i, R_i)，你需要计算满足如下条件的长度为 n 的序列 P 的个数。
  • 对于 \forall i\in[1,n]，有 0\leq P_i\leq A_i。
  • 对于所有偶数下标 i(2\leq i <n)，有 L_i\leq (|P_{i-1}\ - \ P_{i}|\ \oplus \ P_{i+1})\leq R_i。
答案对 10^9 + 7 取模。
\rule{4cm}{0.1pt}
^{\text{∗}} \oplus ：表示按位异或，例如 1\oplus3=2。

输入描述:

本题有多组测试数据

第一行输入一个整数 T(1\leq T \leq 100)，表示数据组数。

对于每组测试数据：

第一行输入一个整数 n(1\leq n\leq 2000)，表示序列长度。

接下来 n 行，每行输入三个整数 A_i(0\leq A_i< 2^{10})，L_i,R_i(0\leq L_i\leq R_i<2^{10})，表示限制条件。

保证 \sum n \leq 2000。

输出描述:

对于每组测试数据，输出满足条件长度为 n 的序列 P 的个数。
示例1

输入

复制 
5
3
0 0 1
1 1 2
2 2 3
2
2 1 12
5 1 12
3
27 130 130
90 23 23
255 214 216
4
80 38 165
130 137 207
165 246 246
164 73 85
5
15 68 246
11 200 200
8 239 240
81 38 119
227 28 111

输出

复制 
3
18
2548
48587550
0

说明

对于第一组测试数据：一共只有 3 种满足条件的序列 P。
P=[0,0,1]：|0-0|\oplus 1=1，1\leq1\leq2。
P=[0,0,2]：|0-0|\oplus 2=2，1\leq2\leq2。
P=[0,1,0]：|0-1|\oplus 0=1，1\leq1\leq2。