题目描述

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

输入格式

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

输出格式

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

样例 1

3 10

5

692707 470472961806427201

470453944730018769

数据范围与提示

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