Counting Positive Integer Solutions

Solve the following problem:

Given two positive integers k and x (with k ≥ 2), define the function:

\( g(x)=x^x \bmod 1000 \)

Count the number of solutions in positive integers \(a_1, a_2, \ldots, a_k\) to the equation:

\( a_1+a_2+\cdots+a_k=g(x) \)

Note: A solution is a k-tuple of positive integers whose sum equals \( g(x) \). For example, when k = 3 and x = 2, we have \( g(2)=2^2 \bmod 1000=4 \), and the valid solutions are:

a1 = 1, a2 = 1, a3 = 2
 a1 = 1, a2 = 2, a3 = 1
 a1 = 2, a2 = 1, a3 = 1

You may recall that the number of ways to write a positive integer \( S \) as a sum of \( k \) positive integers is given by the combinatorial formula \( \binom{S-1}{k-1} \) (provided that \( S \ge k \)); otherwise, the answer is 0.

inputFormat

The input consists of two space-separated positive integers: k and x.

Constraints: k ≥ 2 and x is a positive integer.

outputFormat

Output a single integer, the number of positive integer solutions of the equation.

sample

3 2

3