A number, ${x}$, is called irresponsible when adding ${x}$ to $x+1$ requires a carry operation. For example, $5$, $17$, and ${91}$ are irresponsible numbers because adding them to ${6}$, ${18}$, and $92$ (respectively) requires a carry operation:

In $5+(5+1)=5+6=11$, a ${1}$ is carried over into the $10$'s place. 
In $17+(17+1)=17+18=35$, a $2$ is carried over into the $10$'s place.
In $91+(91+1)=91+92=183$, a ${1}$ is carried over into the $\left(\begin{array}{c c}{{1}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ \end{array}\right).$'s place.

You have two integers, ${x}$ and $n$. Construct a new number, ${s}$, by repeating ${x}$ a total of $n$ times. For example, if $x=3121$ and $n=4$, then $s=3121312131213121$.

Given ${x}$ and $n$, construct ${s}$ and find all the irreponsible numbers between ${1}$ and ${s}$. Then print the number of irresponsible numbers in the aforementioned range; as this number can be quite large, your answer must be modulo $10^9+7$.

Input Format

A single line with two space-separated integers denoting the respective values of ${x}$ and $n$.

Constraints

$1\leq x\leq10^{1,000,000}$
$1\leq n\leq10^{18}$

Subtasks

For $15\%$ of the maximum score: 

$1\leq x\leq10^{6}$
$n=1$

For ${40\%}$ of the maximum score: 

$1\leq x\leq10^{1,000,000}$
$n=1$

Output Format

Print a single integer denoting the number of irresponsible numbers between ${1}$ and ${s}$, modulo $10^9+7$.

Sample Input
1 2

Sample Output
4

Explanation

When we repeat $x=1$ a total of $n=2$ times we get ${11}$. The irresponsible numbers between ${1}$ and ${11}$ are $5$, ${6}$, $7$, and $8$. Because there are four irresponsible numbers, we print $4\times(10^9+7)=4$ on a new line.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Combinatorics


Solutions:
import sys
mod = 7 + 10 ** 9

def f_B(m):
	if m <= 0:
		return 0
	a = B >> 1
	b = B + 1 >> 1
	return ((B - 1) * pow(B, m - 1, mod) - a * pow(b, m - 1, mod)) % mod

def F(n, B=10):
	b = B >> 1
	a = B + 1 >> 1
	if B == 2:
		return (pow(B, n, mod) - 1 - b * n) % mod
	inv = pow(a - 1, mod - 2, mod)
	return (pow(B, n, mod) - 1 - b * inv * (pow(a, n, mod) - 1)) % mod

def is_irresponsible(x, B=10):
	n = len(x)
	x = list(reversed(x))
	y = list(x)
	c = 1
	for i in range(n):
		(c, y[i]) = divmod(y[i] + c, B)
	if c > 0:
		y.append(c)
	for i in range(n):
		if x[i] + y[i] >= B:
			return True
	return False

def count_irr(d, B=10):
	N = len(d)
	a = B + 1 >> 1
	b = B >> 1
	ans = 0
	idx = N - 1
	for i in range(N):
		if d[i] >= a:
			idx = i
			break
	if is_irresponsible(d, B):
		ans = 1
	for i in range(idx + 1):
		delta_i = min(d[i], b)
		if d[i] > delta_i:
			ans = (ans + (d[i] - delta_i) * pow(B, N - 1 - i, mod)) % mod
		if delta_i > 0:
			ans = (ans + delta_i * F(N - 1 - i, B)) % mod
	for i in range(idx + 1, N):
		ans = (ans + d[i] * pow(B, N - 1 - i, mod)) % mod
	return ans

def solve(d, rep, B=10):
	N = len(d)
	a = B + 1 >> 1
	b = B >> 1
	ans = 0
	idx = N
	for i in range(N):
		if d[i] >= a:
			idx = i
			break
	if is_irresponsible(d, B) or (2 * d[-1] >= B and rep >= 2 and (len(set(d)) >= 2)):
		ans = 1
	inv_B = pow(pow(B, N, mod) - 1, mod - 2, mod)
	inv_a = pow(pow(a, N, mod) - 1, mod - 2, mod)
	inv = pow(a - 1, mod - 2, mod)
	p_B = pow(B, N * rep % (mod - 1), mod) - 1
	p_a = pow(a, N * rep % (mod - 1), mod) - 1
	if idx <= N - 1:
		for i in range(idx + 1):
			delta_i = min(d[i], b)
			if d[i]:
				ans = (ans + d[i] * pow(B, N - i - 1, mod) * p_B * inv_B) % mod
			if delta_i:
				pp = pow(a, (N * rep - 1 - i) % (mod - 1), mod) - 1
				ans = (ans - delta_i * (1 + b * pp * inv)) % mod
		for i in range(idx + 1, N):
			if d[i]:
				ans = (ans + d[i] * pow(B, N - i - 1, mod) * p_B * inv_B) % mod
	else:
		(T, D) = (0, 0)
		for i in range(N):
			delta_i = min(d[i], b)
			if d[i]:
				ans = (ans + d[i] * pow(B, N - 1 - i, mod) * p_B * inv_B) % mod
			if delta_i:
				T = (T + delta_i * pow(a, N - i - 1, mod) * p_a * inv_a) % mod
				D = (D + delta_i * rep) % mod
		ans = (ans - D - b * inv * (T - D)) % mod
	return ans
(x, rep) = sys.stdin.readline().strip().split()
x = list(map(int, x))
print(solve(x, int(rep)))