Pairwise Product Subset Sum Modulo

You are given an integer ( M ) and an array of integers. Your task is to calculate the sum of the products of all pairs of distinct elements taken two at a time from the array, and then output the result modulo ( M ). Formally, if the array is denoted as ( a[0],a[1],\dots,a[n-1] ), you need to compute:

[ S = \left( \sum_{0 \le i < j < n} a[i] \times a[j] \right) \bmod M ]

If the array has fewer than 2 elements, the output should be 0.

The input is provided via standard input (stdin) and the output must be printed to standard output (stdout).

inputFormat

The first line contains a single integer ( M ). The second line contains space-separated integers representing the array. The array may be empty, in which case the second line will be empty.

outputFormat

Output a single integer: the computed sum of the product of all pairs of elements modulo ( M ).## sample

5
1 2 3

1