Zhuge Liang‘s Stone Sentinel Maze

Problem Description

Zhuge Liang was a chancellor of the state of Shu Han during the Three Kingdoms period of Chinese history. He is often recognized as the greatest and most accomplished strategist of his era. He was so smart that his name also means “wise man” in Chinese.

One of Zhuge Liang’s achievements in legend is the Stone Sentinel Maze. It was an array of rocks and boulders built to defend against enemies. The formation was located on Yufu Shore by the Yangtze River near present-day Baidicheng, Chongqing, China, where supposed ruins of the array exist.

In chapter 84 of the historical novel Romance of the Three Kingdoms, as Lu Xun neared Baidicheng, he felt a strong enemy presence in the area and alerted his army to a possible ambush. He sent scouts ahead, who reported that the region was deserted except for some scattered piles of rocks. The bewildered Lu Xun asked a local, who told him that qi ("energy") started emerging from the area after Zhuge Liang arranged the rocks there. Lu Xun personally inspected the area and decided that the array was only a petty display of deception. Hence, Lu Xun led a few horsemen with him into the maze, and as he was about to exit, there was a strong gust of wind. At that moment, dust storms overshadowed the sky and the rocks appeared to become valleys; mountainous piles of dirt emerged and the roar of thunder rocked the skies while the waves of the nearby Yangtze River sounded like the clashing of swords and beating of war drums…

After the research on the Stone Sentinel Maze, scientists find some regulations. The rocks have m different kinds of weight (1<=m<=10,000). The weight of a rock is a positive integer not exceeding 10,000. There are n (3<=n<=100,000) rocks placed on a circle with equal spacing and the greatest common divisor of their weight is 1. They want to know in how many ways the rocks can be placed like that.

Notice:
1. Multiple rocks with the same weight can be placed on the circle.
2. If a solution will be the same as another one by rotation, these two solutions should be consider as the same.
3. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10,007.

 

Input

The input begins with a line containing an integer T, the number of test cases.
For each case, the first line begins with two integers --- the above mentioned m and n. Then m lines follow, each containing a positive integer representing rock weight. It is guaranteed that these m integers are different.

 

Output

For each case, output one integer in one line, representing the remainder of the number of ways when divided by 10,007.

 

Sample Input

 

Sample Output

 

Source

The 36th ACM/ICPC Asia Regional Beijing Site —— Online Contest

 

 

题意：给你m种石头子，每种无限多个，选出n个构成环，满足GCD（a1,a2,,,an）=1;

        如果通过旋转相同，看成一种。