#10231. 「一本通 6.6 练习 2」方程的解

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

佳佳碰到了一个难题,请你来帮忙解决。对于不定方程 a_1+a_2+\cdots +a_{k-1}+a_k=g(x) ,其中 k\ge 2 k\in \mathbb{N}^* x 是正整数, g(x)=x^x \bmod 1000 (即 x^x 除以 1000 的余数), x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说,当 k=3,x=2 时,方程的解分别为:

\begin{cases} a_1=1\\ a_2=1\\ a_3=2 \end{cases} \ \ \ \ \begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases} \ \ \ \ \begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases}

输入格式

有且只有一行,为用空格隔开的两个正整数,依次为 k,x

输出格式

有且只有一行,为方程的正整数解组数。

样例

样例输入

3 2

样例输出

3

数据范围与提示

对于 40\% 数据,答案不超过 10^{16}
对于全部数据, 1\le k\le 100,1\le x\lt 2^{31},k\le g(x)