A. 魔法练习
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

欢迎来到北京理工大学第十一届程序设计新生赛！作为北理工的新生，想必大部分同学对魔法（模法）并不是很熟悉，因此接下来将教大家一些基本的魔法技巧，希望你能在本场比赛中用到。

首先，让我们复习一下C语言程序设计的基本知识——基本数据类型能存储的数值范围：

  • int：32位有符号整数，可以表示 $$$-2^{31} \sim 2^{31}-1$$$ 范围内的整数（$$$2^{31} = 2,147,483,648$$$）
  • long long：64位有符号整数，可以表示 $$$-2^{63} \sim 2^{63}-1$$$ 范围内的整数（$$$2^{63} = 9,223,372,036,854,775,808$$$）

同时，介绍一个基本的标记： $$$x\ {\rm mod}\ y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数，读作 $$$x$$$ 模 $$$y$$$ 。在 C/C++ 中，你可以使用 $$$a \% b$$$ 求出 $$$a$$$ 除以 $$$b$$$ 的余数。

对于任意的正整数 $$$x,y,p$$$ ，以下公式总是成立：

  • $$$(x+y)\ {\rm mod}\ p = ((x\ {\rm mod}\ p)+(y\ {\rm mod}\ p))\ {\rm mod}\ p$$$
  • $$$(x \times y)\ {\rm mod}\ p = ((x\ {\rm mod}\ p) \times (y\ {\rm mod}\ p))\ {\rm mod}\ p$$$

因此，如果你试图求一个很大的数字除以 $$$p$$$ 的余数，你可以放心的在过程中的每次运算后都对 $$$p$$$ 取模，以防止数值超出数据类型能够表示的范围。

现在，我们来做一个小练习。给定长度为 $$$n$$$ 的数组 $$$a$$$ ，你需要求出 $$$a$$$ 中所有元素的乘积除以 $$$p$$$ 的余数。

Input

第一行两个整数 $$$n,p$$$ ($$$1 \le n \le 10^5, 1 \le p \le 10^9$$$) ，表示数组 $$$a$$$ 的长度，以及所求答案的除数。

第二行 $$$n$$$ 个整数，第 $$$i$$$ 个整数为 $$$a_i(0 \le a_i \lt p)$$$ ，表示数组中的第 $$$i$$$ 个元素。

Output

输出一行一个整数，表示数组 $$$a$$$ 中所有元素的乘积除以 $$$p$$$ 的余数。

Examples
Input
3 2035
2023 6 3
Output
1819
Input
3 1000000000
999999999 999999998 999999997
Output
999999994
Note

在样例 $$$1$$$ 中，$$$2023 \times 6 \times 3 = 36414$$$ ，$$$36414 \div 2035 = 17 \cdots 1819$$$ ，因此你需要输出 $$$1819$$$ 。

在样例 $$$2$$$ 中，两个数的乘积会超出 int 类型的范围，因此你应该使用 long long 类型。同时，三个数的乘积超出了 long long 类型的表示范围，因此你需要在每次乘完后，把答案对 1000000000 取模。如果你的程序输出了 '-957777926' ，说明你没有使用 long long 类型计算乘积。如果你的程序输出了 '265065466' ，说明你没有在计算过程中及时对结果取模，导致了 long long 类型的溢出。