Tachibana Kanade likes Mapo Tofu very much. One day, the canteen cooked all kinds of tofu to sell, but not all tofu is Mapo Tofu, only those spicy enough can be called Mapo Tofu.
Each piece of tofu in the canteen is given a m-based number, all numbers are in the range [l,r] (l and r being m-based numbers), and for every m-based integer in the range [l,r], there exists a piece of tofu with that number.
To judge what tofu is Mapo Tofu, Tachibana Kanade chose n m-based number strings, and assigned a value to each string. If a string appears in the number of a tofu, the value of the string will be added to the value of that tofu. If a string appears multiple times, then the value is also added that many times. Initially the value of each tofu is zero.
Tachibana Kanade considers tofu with values no more than k to be Mapo Tofu. So now Tachibana Kanade wants to know, how many pieces of tofu are Mapo Tofu?
Output
Output the number of pieces of Mapo Tofu modulo
1000000007 (109+7). The answer should be a decimal integer.
Note
In the first sample, 10, 11 and 100 are the only three decimal numbers in
[1,100] with a value greater than 1. Here the value of 1 is 1 but not 2, since numbers cannot contain leading zeros and thus cannot be written as "
01".
In the second sample, no numbers in the given interval have a value greater than 12.
In the third sample, 110000 and 110001 are the only two binary numbers in the given interval with a value no greater than 6.