Numere

numere

Zaharel is a big fan of numbers. Today he's playing with numbers that have N digits and are written in base B. Be there NR=x₀x₁...x_N-1 such a number in base B (x₀,x₁ etc. represent the digits of number NR written from left to right), we define the image of this number as being number I(NR)=i₀i₁…i_N-2 with the property that i_p=min(x_p,x_p+1). Having a lot of free time, Zaharel has thought about calculating for each possible number of N digits in base B the product of the digits of the number's image and adding these values up.

Task

Write a program that spares Zaharel of these calculations and determines this sum in a reasonable amount of time.

Input Data

The first line of input file numere.in contains the two positive integers N, B, separated by a single space.

Output Data

The first line of file numere.out will contain the sum Zaharel is looking for. Because the result can be very large, displaying just the remainder of dividing the result to 666013 is enough.

Constraints

2 <= N <= 20000
2 <= B <= 1000
The numbers can begin with 0.

Examples

numere.in

numere.out

Explanation

2 4

NR=00, I(NR)=0, we add 0

NR=01, I(NR)=0, we add 0

NR=02, I(NR)=0, we add 0

NR=03, I(NR)=0, we add 0

NR=10, I(NR)=0, we add 0

NR=11, I(NR)=1, we add 1

NR=12, I(NR)=1, we add 1

NR=13, I(NR)=1, we add 1

NR=20, I(NR)=0, we add 0

NR=21, I(NR)=1, we add 1

NR=22, I(NR)=2, we add 2

NR=23, I(NR)=2, we add 2

NR=30, I(NR)=0, we add 0

NR=31, I(NR)=1, we add 1

NR=32, I(NR)=2, we add 2

NR=33, I(NR)=3, we add 3

Time limit: 1.8 seconds/test

Mircea Paşoi
University of Bucharest, Mathematics & IT Department
bogdanpasoi@yahoo.com