该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

中州东部，有一个矮人的国度。

这个国度有 $n$ 个城市，每个城市有一个势力值，第 $i$ 个城市的势力值为 $a_i$。

现在你想知道这个国度的势力值，即

$$\Big(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i +1}^{n}a_i\times a_j\Big) \bmod P$$

输入格式

第一行两个整数 $n,P$，表示序列的长度和模数。

第二行 $n$ 个正整数，表示序列 $A$。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

4 1000000007

3 4 5 4

样例输出 #1

95

提示

样例 $1$ 解释：

答案等于 $3\times 4+4\times5+3\times5=12+20+15=47$。

数据范围

子任务	测试点	$n\le$	$P=$	$a_i\le$	分数
$1$	$1,2$	$10^2$	$1007$	$10^2$	$10$
$2$	$3-7$	$5\times10^3$	$911451407$	$10^5$	$15$
$3$	$8-12$	$10^5$	$10^9+9$		$30$
$4$	$13-16$		$10^9+7$	$10^9$	$20$
$5$	$17-23$	$2\times10^5$	$10^{11}+3$		$25$

对于子任务 $4$：$a_1=a_2=\dots=a_n$。

对于所有数据： $1\le n\le 2\times10^5,1\le a_i\le10^9,P$ 的值由上表给出。