Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Beautiful Numbers
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 647Accepted: 140

Description

Now that you believe Jiajia & Wind's cute daughter, Autumn, is a genius. It's not surprising that such a clever little girl would have no interest on simple additions very soon. This time, she turned to divisions, since they're more fun. For example, she found herself that if the sum of digits of a decimal number is a multiple of 3, then the decimal number itself is also a multiple of 3. The argument is still true if she replaces the number 3 with 9.

Inspired by these, Autumn invented a special kind of number, called 'Beautiful Numbers'. A number k is said to be Beautiful in base b, if the sum of digits of k in base b is a multiple of b.

Autumn knows how to calculate the sum of first n beautiful numbers in base b, can you?

Input

The input contains a single test case with two lines. The first line is a single integer n(n < 101001), the second line is a single integer b(1 < b < 1001).

Output

The output contains a single integer, the sum of first n beautiful numbers in base b. You should output the sum in decimal, not in base b.

Sample Input

2
3

Sample Output

12

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator