Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3061
Function

Time Limit: 3 Seconds      Memory Limit: 32768 KB

Define a function f(i), where i is an positive integer which can be write as a 3-base integer (an..a2a1a0)3. Assuming aj equals to 2 and there doesn't exists ak that ak equals to 2 and k > j, then f(i) = (an..aj+1)3. For example, 142 = (12021)3, f(142) = (1)3 = 1. If j doesn't exists, then f(i) = i. If j equals to n, then f(i) = 0.

Your task is to calculate the sum from f(1) to f(n) for given integer n.

Input

In each line, there is two positive integer 1 <= n <= 1000000000, 1 <= k <= 10000.

Output

Print the sum module k in a single line.

Sample Input

1 100
2 100
3 100
100 13

Sample Output

1
1
4
10

Author: ZHANG, Rui
Source: ZOJ Monthly, November 2008
Submit    Status