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 ( ≤ 10²⁰, in the system of base K)

Output

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

2 101

1

Hint

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

Source

POJ Founder Monthly Contest – 2008.03.16, ShiningMoon