题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Permutacja

多重集的排列是指将多重集中的元素按一定顺序排列形成的序列。字典序中，一个排列小于另一个排列，若在首次不同的位置上前者元素更小。所有排列可按字典序从 1 开始编号。需计算给定排列的编号对 m 取模的结果。

输入格式

1. 第一行：两个整数 n 和 m（1 ≤ n ≤ 300000，2 ≤ m ≤ 10^9），分别表示元素数量和模数；
2. 第二行：n 个正整数 a_i（1 ≤ a_i ≤ 300000），表示给定的多重集排列。

输出格式

输出一行整数，为该排列的字典序编号对 m 取模的结果。

样例

输入

4 1000
2 1 10 2

输出

5