
ZOJ Problem Set  3061
Define a function f(i), where i is an positive integer which can be write as a 3base integer (a_{n}..a_{2}a_{1}a_{0})3. Assuming a_{j} equals to 2 and there doesn't exists a_{k} that a_{k} equals to 2 and k > j, then f(i) = (a_{n}..a_{j+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 