3869：Color the Simple Cycle

Consider a simple cycle with N vertices numbered from 1 to N. Each vertex and Each edge has an integer value. We use v[k] to represent the kth vertex's value, and e[k] to represent the kth edge's value. The kth edge is the edge of the kth and the (k+1)th vertex (the (N+m)th vertex is the mth vertex). Now we will use C different colors to color the graph. Every vertice will be colored by one of the C colors. If there exists some integer number k which satisfies v[i]=v[i+k] and e[i]=e[i+k] for each i from 1 to N(v[N+t]=v[t] and e[N+t]=e[t]), we call the graph is the same under k rotation.
If two ways of coloring the cycle can be the same with some rotation and under that rotation the color of the corresponding vertices are also the same, we consider the two ways are the same ways. Given the simple cycle and the number of colors we will use, how many different ways to color the cycle?

First comes an integer T representing the number of test cases. Each case consists of three lines. First line contains N(1<=N<=100000) and C (1<=C<=1000000). Second line contains N integer numbers representing the vertex's values. The last line of each case contains N integer numbers representing the edge values. Each value is between 1 and 1000000.

For each case, print a line with the different ways of coloring the cycle mod 1000000007.