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