P17254 Linear Sieve 2

**Stealing the testdata and directly printing the output to grab the best solution is a serious violation. Depending on the severity, your account may be permanently banned.** > It got dark. > Then it got bright again. > The sun shines on this lowland, > shining on every tiny and precious life.

Given a multiplicative function $f$ and a modulus $P$, for each $1 \le n \le N$, compute $f(n)^n \bmod P$.

The first line contains two positive integers $N, P$. Then there are $\pi(N)$ lines. On the $i$-th line there are $\left\lfloor\log_{p_i}N\right\rfloor$ integers; the $j$-th integer is $f(p_i^j)$, where $p_i$ is the $i$-th prime.

Output one non-negative integer, which is $\displaystyle\bigoplus_{n=1}^N (f(n)^n \bmod P)$.

For all testdata, $1 \le N \le 3 \times 10^7$, $10^8 \le P \le 10^9$, $0 \le f(p^k) < P$, and it is **not guaranteed** that $P$ is prime. The time limit has been increased to more than $1.5$ times that of std. Translated by ChatGPT 5