using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 10");
WillReturn.Add("4 2 3 2");
//20
}
else if (InputPattern == "Input2") {
WillReturn.Add("20 100");
WillReturn.Add("29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8");
//1733
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mN;
static long mM;
static long[] mAArr;
struct EdgeInfoDef
{
internal long FromNode;
internal long ToNode;
internal long Cost;
}
static List<EdgeInfoDef> mEdgeInfoList = new List<EdgeInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
mN = wkArr[0];
mM = wkArr[1];
mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
for (long I = 0; I <= mAArr.GetUpperBound(0); I++) {
for (long J = I + 1; J <= mAArr.GetUpperBound(0); J++) {
EdgeInfoDef WillAdd;
WillAdd.FromNode = I + 1;
WillAdd.ToNode = J + 1;
long Kou1 = DeriveBekijyou(mAArr[I], mAArr[J], mM);
long Kou2 = DeriveBekijyou(mAArr[J], mAArr[I], mM);
WillAdd.Cost = (Kou1 + Kou2) % mM;
mEdgeInfoList.Add(WillAdd);
}
}
// クラスカル法で解く
var InsUnionFind = new UnionFind();
for (long I = 1; I <= mN; I++) {
InsUnionFind.MakeSet(I);
}
// 枝をコストの降順にソート
mEdgeInfoList.Sort((a, b) => b.Cost.CompareTo(a.Cost));
long SumCost = 0;
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoList) {
long FromNode = EachEdgeInfo.FromNode;
long ToNode = EachEdgeInfo.ToNode;
long RootNode1 = InsUnionFind.FindSet(EachEdgeInfo.FromNode);
long RootNode2 = InsUnionFind.FindSet(EachEdgeInfo.ToNode);
if (RootNode1 != RootNode2) {
InsUnionFind.Unite(FromNode, ToNode);
SumCost += EachEdgeInfo.Cost;
}
}
Console.WriteLine(SumCost);
}
// 繰り返し2乗法で、(NのP乗) Mod Mを求める
static long DeriveBekijyou(long pN, long pP, long pM)
{
long CurrJyousuu = pN % pM;
long CurrShisuu = 1;
long WillReturn = 1;
while (true) {
// 対象ビットが立っている場合
if ((pP & CurrShisuu) > 0) {
WillReturn = (WillReturn * CurrJyousuu) % pM;
}
CurrShisuu *= 2;
if (CurrShisuu > pP) return WillReturn;
CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
}
}
}
#region UnionFind
// UnionFindクラス
internal class UnionFind
{
private class NodeInfoDef
{
internal long ParentNode;
internal long Rank;
}
private Dictionary<long, NodeInfoDef> mNodeInfoDict =
new Dictionary<long, NodeInfoDef>();
// 要素が1つである木を森に追加
internal void MakeSet(long pNode)
{
NodeInfoDef WillAdd = new NodeInfoDef();
WillAdd.ParentNode = pNode;
WillAdd.Rank = 0;
mNodeInfoDict[pNode] = WillAdd;
}
// 合併処理
internal void Unite(long pX, long pY)
{
long XNode = FindSet(pX);
long YNode = FindSet(pY);
long XRank = mNodeInfoDict[XNode].Rank;
long YRank = mNodeInfoDict[YNode].Rank;
if (XRank > YRank) {
mNodeInfoDict[YNode].ParentNode = XNode;
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
if (XRank == YRank) {
mNodeInfoDict[YNode].Rank++;
}
}
}
// ノードを引数として、木の根を取得
internal long FindSet(long pTargetNode)
{
// 根までの経路上のノードのList
var PathNodeList = new List<long>();
long CurrNode = pTargetNode;
while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
PathNodeList.Add(CurrNode);
CurrNode = mNodeInfoDict[CurrNode].ParentNode;
}
// 経路圧縮 (親ポインタの付け替え)
foreach (long EachPathNode in PathNodeList) {
mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
}
return CurrNode;
}
internal void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
}
#endregion