numere

Цифърко е голям фен на числата. Днес той играе с числа, които имат N цифри и които са записани в бройна система с основа B. Нека NR=x0x1...xN-1  е такова число, записано в бройна система с основа B (x0,x1 и т.н. представят цифрите на числото NR, записани отляво-надясно). Ние дефинираме образ на това число като друго число I(NR)=i0i1iN-2 за което е изпълнено, че  ip=min(xp,xp+1). Имайки много време, Цифърко  е започнал да мисли как да пресмята за всяко възможно число от N цифри при основа B произведенията на цифрите на образа му и да получава сумата на тези произведения.

Задача

Напишете програма, която да помага на Цифърко да прави такива пресмятания и да намира търсената сума за приемливо време.  

Вход

Единственият ред на входния файл numere.in съдържа две положителни цели числа N и B, отделени с един интервал.

Изход

Единственият ред на изходния файл numere.out трябва да съдържа сумата, която Цифърко търси. Понеже резултатът може да е много голям, достатъчно е да се изведе само остатъкът от делението на резултата с числото 666013.

Ограничения

2 <= N <= 20000
2 <=
B <= 1000
Числата може да започват с 0.

Примери

numere.in

numere.out

Обяснение

2 4

 

14

NR=00, I(NR)=0, прибавяме 0

NR=01, I(NR)=0, прибавяме 0

NR=02, I(NR)=0, прибавяме 0

NR=03, I(NR)=0, прибавяме 0

NR=10, I(NR)=0, прибавяме 0

NR=11, I(NR)=1, прибавяме 1

NR=12, I(NR)=1, прибавяме 1

NR=13, I(NR)=1, прибавяме 1

NR=20, I(NR)=0, прибавяме 0

NR=21, I(NR)=1, прибавяме 1

NR=22, I(NR)=2, прибавяме 2

NR=23, I(NR)=2, прибавяме 2

NR=30, I(NR)=0, прибавяме 0

NR=31, I(NR)=1, прибавяме 1

NR=32, I(NR)=2, прибавяме 2

NR=33, I(NR)=3, прибавяме 3

 Time limit: 1.8 seconds/test

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

 

(превод на български: Емил Келеведжиев)