×

# 计蒜客

1. 题库
2. Convex Hull
3. 问答
• 18.94%
• 1500ms
• 131072K

We define a function $gay(i)$:

$$\displaystyle gay(i)=\left\{ \begin{array}{rcl} & 0, \quad& if \quad i = k*x*x, x > 1, k \geq 1 \\ & i * i ,\quad& else \end{array} \right.$$

Now your task is to calculate$$\displaystyle \sum_{num=1}^n (\sum_{i=1}^{num} gay(i)) \mod p$$

### Input

Multiple test cases. Please use EOF.

In each test case, there are two integers $n$, $p$, which are described above.

$1 \leq n \leq 10^{10},1 \leq p \leq 10^{11}$.

The number of test cases is no more than $100$.

### Output

For each test case print the answer in one line.

#### 样例输入

1 10
8 19230817

#### 样例输出

1
396

• main.c