小 X は $n$ 種類の色のボールを持っており、そのうち $i$ 番目の色のボールは合計 $a_i$ 個あります。同じ色のボールは区別できません。$l$ 番目から $r$ 番目までの色のボールの「混乱度」 $f(l, r)$ を、これら $l$ から $r$ までのすべてのボールを一列に並べる並べ方の総数を $p$ で割った余りと定義します。小 X は、以下の式の値を計算してほしいと考えています。

$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) $$

入力

第一行に2つの整数 $n, p$ が与えられます。

第二行に $n$ 個の整数 $a_i$ が与えられます。

出力

答えを1行で出力してください。

入出力例

入力 1

2 2
1 2

出力 1

3

注記 1

$$f(1,1) = 1 \bmod 2 = 1$$

$$f(1,2) = 3 \bmod 2 = 1$$

$$f(2,2) = 1 \bmod 2 = 1$$

$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) = 3$$

入力 2

4 7
1 2 8 9

出力 2

28

入力 3

15 5
1 5 26 1 0 5 0 6 7 51 1 5 26 1 0

出力 3

124

小課題

本問題はバンドルテスト方式を採用しています。

• Subtask 1（31点）：$1 \le n \le 5 \times 10^5$、$a_i$ は $[0, 10^5]$ の範囲で一様ランダム。制限時間 $1.5 \text{ s}$。
• Subtask 2（32点）：$1 \le n \le 5 \times 10^4$。制限時間 $5 \text{ s}$。
• Subtask 3（37点）：特別な制限なし。制限時間 $2.5 \text{ s}$。

すべてのデータにおいて、$1 \le n \le 5 \times 10^5$、$0 \le a_i \le 10^{18}$、$p \in \{2,3,5,7\}$ です。