{"raw_statement":[{"iden":"background","content":"少年身着春季校服的深灰色外套与黑色短裤，外套内是白净的衬衫。\n\n他的右手不知为何缠着绷带，右眼用头发挡得严严实实，扑面而来的是一种神秘感。\n\n一瓣鲜红的彼岸花，在教室上空无人在意之处打旋。\n\n玘的身世，总是一个谜题吧。\n\n「所以你到底是什么人，又为什么要来这里！」\n\n可是彼岸花显然不想让你知道这些。"},{"iden":"statement","content":"玘给了寒一棵编号为 $1\\sim n$ 的树，这棵树上每个点都有一个点权，同时有些边有边权，有些边没有边权。可是玘把每一个点的点权删除了。寒只知道****点权都是整数，而且在 $l$ 和 $r$ 之间（包含端点）****。而且，点权和边权有着下面的特殊关系：\n\n- 对于****有边权****的边，要求****连接的两个点的点权和为边权****。\n\n- 对于****没有边权的边****，****无限制****。\n\n玘问寒这棵树****有多少种不同的点权填写方式****。两种填写方式不同，当且仅当至少存在一个点的点权不同。可是寒不会做这个题。\n\n寒请你解决这个问题。"},{"iden":"input","content":"**本题有多组测试数据。**\n\n第一行一个整数 $T$，代表测试数据组数。\n\n对于每一组测试数据：\n\n第一行三个整数 $n,l,r$，代表树上点的个数是 $n$，点权的范围是 $[l,r]$。\n \n接下来 $n-1$ 行，每行先输入一个整数 $op$，$op=0$ 表示这条边没有边权，$op=1$ 表示这条边有边权。\n\n+ 如果 $op=0$，再输入两个整数 $u,v$，表示这条边连接 $u,v$ 两个点。\n\n+ 如果 $op=1$，再输入三个整数 $u,v,w$，表示有一条权值为 $w$ 的边连接 $u,v$ 两个点。"},{"iden":"output","content":"对于每个测试点，输出一行一个整数，代表点权填写方式的个数。答案对 $10^9+7$ 取模。"},{"iden":"note","content":"**样例解释**\n\n对于样例的第一组测试数据，可以得到下图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/91vlqt5k.png)\n\n$5$ 种填写方式分别为：\n\n$\\{0,2,2,0,0,3\\}\\\\\\{0,2,2,0,1,3\\}\\\\\\{0,2,2,0,2,3\\}\\\\\\{0,2,2,0,3,3\\}\\\\\\{0,2,2,0,4,3\\}$\n\n可以证明，不存在别的填写方式。\n\n样例输入中，为了直观，添加了空行。实际数据中不存在多余空行。\n\n**数据范围**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 数据范围 | 特殊性质 | 分值 |\n| :-----------: | :-----------: | :-----------: | :-----------: |\n| $\\text{Subtask1}$ | $1\\le n\\le 10$，$0\\le l,r\\le5$ |  | $15$ |\n| $\\text{Subtask2}$ | $1\\le n\\le 2\\times 10^5$，$0\\le l,r\\le5$ |  | $20$ |\n| $\\text{Subtask3}$ | $1\\le n\\le 10$，$-10^9\\le l,r\\le 10^9$ |  | $15$ |\n| $\\text{Subtask4}$ | $1\\le n\\le 2\\times10^5$，$-10^9\\le l,r\\le 10^9$ | 有 | $10$ |\n| $\\text{Subtask5}$ | $1\\le n\\le 2\\times10^5$，$-10^9\\le l,r\\le 10^9$ |  | $40$ |\n\n特殊性质：保证每条边都无边权。\n\n对于 $100\\%$ 的数据，保证 $1\\le T \\le 5$，$1\\le n\\le 2\\times10^5$，$1\\le \\sum n\\le 10^6$，$-10^9\\le l\\le r \\le 10^9$，$-10^9\\le w\\le 10^9$，$op\\in\\{0,1\\}$。"}],"translated_statement":null,"sample_group":[["2\n6 0 4\n1 1 2 2\n1 2 3 4\n1 3 4 2\n0 2 5\n1 4 6 3\n\n6 -1 4\n1 1 2 4\n0 2 3\n0 3 4\n0 2 5\n0 4 6","5\n6480"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}