女神的正多面体

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      EOF女神灰常喜欢整齐的东西,例如多面体中最喜欢的就是正多面体。正多面体的定义为:指每个面都是全等的正多边形的多面体。欧拉大人告诉我们,正多面体只有正四面体(正三棱锥),正六面体(立方体),正八面体(钻石?),正十二面体,还有正二十面体。后面两种太复杂了,EOF女神不喜欢。下面是前三种多面体的图片,EOF女神给每个多面体的每个顶点都编号了。

    EOF女神想知道,如果从其中一个点出发,每一步可以沿着棱走到另一个顶点,k步之内从到达指定的顶点有多少种走法?(P.S.路径中只要有一个顶点不一样即视为不同的走法)。EOF女神知道结果会很庞大,因此只要知道除以1000000007的余数就可以了。

Input

    先输入一个正整数T,表示测试数据的组数。

    接下来是T行,每行包括四个正整数n,k,i,j,其中n∈{4,6,8},表示正多面体的种类,i为起点的编号,j为终点的编号,k为步数(k<=10^18)

Output

    输出T行,每行输出一个整数,表示方法数。(记得要取余哦~)

Sample Input

3
6 1 8 4
6 2 3 1
8 3 2 4

Sample Output

1
2
12

Hint

第二组样例,有3->2->1与3->4->1两种方法

第三组样例,有2->1->4、2->3->4、2->5->4、2->6->4、2->1->3->4、2->1->5->4、2->3->1->4、2->3->6->4、2->5->1->4、2->5->6->4、2->6->3->4、2->6->5->4这12种方法

Source

mathlover

Manager

Information
Solved Number40
Submit Number164
Problem Tags
matrices
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel