Background

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.

Problem Description

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

Input Format

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 Format

Output one non-negative integer, which is $\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

Hint

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