Description

给你一棵n个节点的树，每个节点都有一个小于m的权值

定义一棵子树的权值为所有节点的异或和，问权值为0..m−1的所有子树的个数

Format

Input

第一行给出T，代表数据组数 对于每组数据，第一行给出N，M 接下来N－１行描述这个树 T<=10

N<=1000

1<=M<=2^10,并且M一定可表示成2^K,K为非负整数

Output

见样例,输出结果%(1e9+7)

Samples

2
4 4
2 0 1 3
1 2
1 3
1 4
4 4
0 1 3 1
1 2
1 3
1 4

3 3 2 3
2 4 2 3