[AdditionalFile6740.zip](file://AdditionalFile6740.zip?type=additional_file)

#6740. 费马大定理

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

给出质数 $p$，求有多少个正整数 $k\le n$ 满足存在 $0<x,y,z<p$ 使 $x^k+y^k\equiv z^k\pmod p$。

输入格式

一行两个正整数 $p,n$。

输出格式

一行一个正整数，为答案。

样例 1

输入

3 10

输出

5

样例 2

输入

692707 470472961806427201

输出

470453944730018769

数据范围与提示

对于 $100\%$ 的数据，$2\le p\le 10^6$，$1\le n\le 10^{18}$。