Product Modulo

Let’s take a prime P = 200,003. You are given N integers A_1, A_2, \ldots, A_N. Find the sum of ((A_i \cdot A_j) \bmod P) over all N \cdot (N-1) / 2 unordered pairs of elements (i < j).

Please note that the sum isn't computed modulo P.

Constraints

• 2 \leq N \leq 200,000
• 0 \leq A_i < P = 200,003
• All values in input are integers.

Input

Input is given from Standard Input in the following format.

N A_1 A_2 \cdots A_N

Output

Print one integer — the sum over ((A_i \cdot A_j) \bmod P).

Examples

Input

4 2019 0 2020 200002

Output

474287

Input

5 1 1 2 2 100000

Output

600013

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format.

N A_1 A_2 \cdots A_N

outputFormat

Output

Print one integer — the sum over ((A_i \cdot A_j) \bmod P).

Examples

Input

4 2019 0 2020 200002

Output

474287

Input

5 1 1 2 2 100000

Output

600013

样例

4
2019 0 2020 200002

474287