Function

Time Limit: Java: 3000 ms / Others: 3000 ms

Memory Limit: Java: 32768 KB / Others: 32768 KB

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

Hint

None

Source

ZOJ Monthly, November 2008

提交代码