P17254 线性筛 2

**套取数据直接输出抢最优解是恶劣的违规行为，根据情节轻重，最高可以直接封号。** > 天黑了。 > 天又亮了。 > 太阳照在这片洼地上， > 照着一切微小而珍贵的生命。

给定积性函数 $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)$。

对于所有数据，$1\le N\le3\times10^7$，$10^8\le P\le10^9$，$0\le f(p^k)