背景

套取数据直接输出抢最优解是恶劣的违规行为，根据情节轻重，最高可以直接封号。

天黑了。
天又亮了。
太阳照在这片洼地上，
照着一切微小而珍贵的生命。

题目描述

给定积性函数 $f$、模数 $P$，对于 $1\le n\le N$ 分别求出 $f(n)^n\bmod P$。

输入格式

第一行两个正整数 $N,P$。

之后 $\pi(N)$ 行，第 $i$ 行 $\left\lfloor\log_{p_i}N\right\rfloor$ 个整数，第 $j$ 个数为 $f(p_i^j)$，其中 $p_i$ 为第 $i$ 个素数。

输出格式

一行一个非负整数，表示 $\displaystyle\bigoplus_{n=1}^N(f(n)^n\bmod P)$。

20 1000000000
2 4 8 16
3 9
5
7
11
13
17
19

501702414

提示

对于所有数据，$1\le N\le3\times10^7$，$10^8\le P\le10^9$，$0\le f(p^k)<P$，不保证 $P$ 是素数。

时限已开至 std 的 1.5 倍以上。