Cherished Time Value Sum

In this problem, you are given two integers n and k. For each second from 1 to n, we first convert the second number into its base‐k representation. In Little L’s world, a minute has k seconds and an hour has k minutes, so time is expressed in base k.

After converting the second i into its base‐k representation (without leading zeros), we treat it as a sequence of digits. Then we define its value as the length of the longest contiguous substring that forms an arithmetic progression. (A contiguous arithmetic progression is defined as a sequence in which the difference between any two consecutive digits is the same. Note that only consecutive digits that are the same single digit are considered, so for example in base 10 the number 123456789101112 does not form a contiguous arithmetic progression because the progression is broken between digits of different numbers.)

For a number with only one digit, its value is defined to be 1. For any number with at least two digits, note that any two adjacent digits form an arithmetic progression (of length 2), so the value is at least 2.

Your task is to compute the sum of the values of all seconds from 1 to n modulo (19260821).

inputFormat

The input consists of a single line containing two space‐separated integers n and k, where 1 (\le) n and k is an integer ((k\ge2)).

outputFormat

Output a single integer: the sum of the values for each second from 1 through n modulo (19260821).

sample

10 10

11