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

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

题目描述

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

举例来说,当 k=3,x=2k=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,xk,x

输出

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

样例

3 2
3

提示

数据范围与提示:

对于 40% 数据,答案不超过 101610^{16}

对于全部数据,1k100,1x<231,kg(x)1≤k≤100,1≤x<2^{31} ,k≤g(x)

来源

一本通在线评测