Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Alternating Sum of Digits
 Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 206 Accepted: 41

Description

Any integer number can be written as a sequence of digits in a specific system of base. For example, 5 in decimal based system can be written as 101 in binary based system. By writting down every number from 1 to N in system of base K one by one, we obtain a long sequence of digits. Your task is to calculate the alternating sum of digits, i.e. the difference between the sum of digits with odd index in the sequence and the sum of ones with even index.

For example, the sequence is 11011100101 and the alternating sum is 1 (the result of +1-1+0-1+1-1+0-0+1-0+1) given K = 2 and N = 101.

Input

K (1 < K ≤ 10) and N ( ≤ 1020, in the system of base K)

Output

The alternating sum. You should print it in decimal based system.

Sample Input

`2 101`

Sample Output

`1`

Hint

It is safe to use 64-bit signed integral arithmetic.

Source

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