Time Limit: 1000MS Memory Limit: 65536 K

## Description

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

## Source

or: ZHANG, Rui
Source: ZOJ Monthly, November 2008