- Practice
- Mathematics
- Number Theory
- Coprime Power Sum

# 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:

- 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).
- 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:

- 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.
- 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.