计数题

小金画了一张图，他先画了$n$个点，记作$1...n$。接着，他依次检查每一个二进制位，如果第$i$个点和第$j$个点（$j$可以等于$i$）满足$i$的二进制形式从低到高第$k$位和$j$的第$k$位相与为$1$（即同时为$1$），就画一条从$i$到$j$的有向边。注意：这张图可以存在重边和自环。

边的添加过程用C语言代码表示即：

int get(int i, int k) { return (i >> k) & 1; }

for (int k = 0; k < 30; k++)
　　for (int i = 1; i <= n; i++)
　　　　for (int j = 1; j <= n; j++)
　　　　　　if ((get(i, k) & get(j, k)) == 1)
　　　　　　　　add_edge(i, j); // 添加一条从$i$到$j$的有向边

多次询问从点$u$出发到达$v$有多少条不同的路径满足长度等于$t$（答案对$1e9+7$取模）
注意：重边视为不同的边，两条路径相同仅当它们经过的边和次序完全相同。

第$1$行给出$n$
第$2$行给出$T$
接下来$T$行给出$u$，$v$，$t$。一行代表一次询问。

$1\le u,v\le n\le 1e5,1\le t\le1e9,1\le T\le 100$

对于每一次询问，输出一个数表示路径条数。答案对$1e9+7$取模

5
3
5 2 1
5 2 2 	
5 2 3

0
1
6

第3个询问：
共有17条边，边分别是：
1 -> 1
1 -> 3
1 -> 5
3 -> 1
3 -> 3
3 -> 5
5 -> 1
5 -> 3
5 -> 5
2 -> 2
2 -> 3
3 -> 2
3 -> 3
4 -> 4
4 -> 5
5 -> 4
5 -> 5
6条路径分别是
5->1->3->2
5->3->2->2
5->3->3->2
5->3->3->2
5->5->3->2
5->5->3->2

"文远知行杯"杭州电子科技大学第二十一届程序设计竞赛