We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Coprime Power Sum

Coprime Power Sum

Given two integers, and , Alice loves to calculate their power sum using the following formula:

Bob has a set, , of distinct pairwise coprime integers. Bob hates multiples of these integers, so he subtracts from Alice's power sum for each whenever there exists at least one such that .

Alice and Bob are now confused about the final value of the power sum and decide to turn to Eve for help. Can you write a program that helps Eve solve this problem? Given queries consisting of , , and , print the value of the power sum modulo on a new line for each query.

Input Format

The first line contains an integer, , denoting the number of queries. The lines describe each query over two lines:

  1. The first line contains three space-separated integers denoting the respective values of (the number of integers in Bob's set), (the exponent variable in the power sum formula), and (the upper range bound in the power sum formula).
  2. The second line contains distinct space-separated integers describing the respective elements in set .

Constraints

Output Format

For each query, print the resulting value of the power sum after Bob's subtraction, modulo .

Sample Input

2
2 1 10
2 3
3 2 18
4 13 9

Sample Output

13
1055

Explanation

We perform the following queries:

  1. Alice first calculates the sum . Bob's set contains and only, so he subtracts the power of all numbers that are multiples of and/or from Alice's sum to get: . We then print the result of on a new line.
  2. Alice first calculates the sum . Bob then subtracts multiples of , , and from Alice's sum to get: . We then print the result of on a new line.