Maximizing Number with Increment Operations

You are given an integer (x) and you need to perform (n) operations on it. In each operation, you can choose an arbitrary base (y) (an integer with (y \ge 2)) and then increment exactly one valid digit of (x) when it is written in base (y). A valid digit is defined as the first nonzero digit (i.e. the most significant digit) and all digits following it. However, you must ensure that the increment will not cause a carry in base (y), i.e. if the digit is (d), you must have (d+1 \le y-1) (or, equivalently, (d < y-1)).

Note that in each operation you can choose a different base (y) (with (y \in [2, +\infty))).

Your task is to maximize the value of (x) after (n) operations and output the maximum value in decimal form modulo (10^9+7).


Observation: One optimal strategy is to choose, in every operation, a base (y = x) (where (x) is the current number). In this case, the base-(x) representation of (x) is (10), so the only digit you can increment is the most significant digit (which is (1), and (1 < x-1) for (x \ge 2)). Incrementing it increases (x) by (x), effectively doubling (x). Repeating this (n) times results in (x \cdot 2^n).

Thus, the answer is (x \cdot 2^n \bmod (10^9+7)).

inputFormat

The input consists of a single line containing two space-separated integers (x) and (n). (x) is the initial number and (n) is the number of operations.

outputFormat

Output a single integer, the maximum value of (x) after (n) operations modulo (10^9+7).

sample

1 3

8