Manasa recently lost a bet to Amit. To settle the problem, they are playing a game:  

They have N balls in front of them. Each ball, except the 1st ball, is numbered from 0 to 9. The 1st ball is numbered from 1 to 9. 

Amit calculates all the subsequences of the number thus formed. Each subsequence of sequence S is represented by S_{k}. 

e.g. S = 1 2 3  

S_{0} = 1 2 3 , 

S_{1} = 1 2 , 

S_{2} = 1 3 , 

S_{3} = 2 3 , 

S_{4} = 1 , 

S_{5} = 2 , and 

S_{6} = 3 .  

Each subsequence S_{k} also represents a number. e.g. S_{1} represents tweleve, S_{2} represents thirteen.

Now Manasa has to throw S_{k} candies into an intially empty box, where k goes from 0 to ( maximum number of subsequences -  1).

At the end of the game, Manasa has to find out the total number of candies, T, in the box. As T can be large, Amit asks Manasa to tell T % (10^{9} + 7 ). If Manasa answers correctly, she can keep all the candies. Manasa can't take all this Math and asks for your help.  

Help her!

Note: A subsequence can also be have preceding zeros. For example, the sequence 103 has subsequences 103, 10, 13, 03, 1, 0, and 3 (so both 03 and 3 are counted separately).

Input Format 

A single line containing a number having N digits.  

Output Format 

A number contaning the output.  

Constraints 

1 ≤ N ≤ 2*10^{5}  

Sample Input 00

111

Sample Output 00

147

Sample Input 01

123

Sample Output 01

177

Explanation  

The subsequence of number 111 are 111, 11 , 11, 11, 1, 1 and 1. Whose sum is 147.

The subsequence of number 123 are 123, 12 , 23, 13, 1, 2 and 3. Whose sum is 177.

Difficulty: MEDIUM
Tags: Matrices

Starter code:

Solutions:
P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


s = input().strip()
n = len(s)
ans = 0
p = int(1000000000.0 + 7)
for i in range(n):
	a = int(s[n - i - 1])
	tmp = a * pow(2, n - 1 - i, p) * pow(11, i, p) % p
	ans += tmp
	ans %= p
print(ans)


from sys import stdin as cin
from math import factorial as f
mod = 1000000007

def substr(string):
	k = len(string)
	c = 0
	for i in range(k):
		c = (c + int(string[i]) * pow(2, i, mod) * (pow(11, k - 1 - i, mod) % mod) % mod) % mod
	return int(c % mod)
a = cin.readline()
print(substr(a))


mod = 10 ** 9 + 7
i = list(input())
(s, n) = (0, 0)
for c in i:
	d = int(c)
	s = (s + s * 10 + d * n + d) % mod
	n = (n * 2 + 1) % mod
print(s % mod)


modulo = 10 ** 9 + 7

def solve(S):
	c = 1
	sum = 0
	for x in reversed(S):
		sum = (2 * sum + int(x) * c) % modulo
		c = c * 11 % modulo
	return sum
print(solve(input()))


n = [int(i) for i in list(input())]
orig = n[0]
for i in range(1, len(n)):
	orig = orig * 11 % 1000000007
	orig += n[i] * pow(2, i, 1000000007)
	orig = orig % 1000000007
print(orig)


n = input()
size = len(n)
ans = 0
for i in range(size):
	pow11 = pow(11, size - i - 1, 1000000007)
	pow2 = pow(2, i, 1000000007)
	ans = (ans + int(n[i]) * pow11 * pow2 % 1000000007) % 1000000007
print(ans)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


MOD = 10 ** 9 + 7
S = input()
print(sum((int(S[i]) * pow(2, i, MOD) * pow(11, len(S) - i - 1, MOD) for i in range(len(S)))) % MOD)


MOD = 10 ** 9 + 7
A = [int(x) for x in list(input().rstrip())]
res = 0
for i in range(len(A)):
	res = (res * 11 + pow(2, i, MOD) * A[i]) % MOD
print(res)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


p = 1000000007
arr = input()
n = len(arr)
print(sum((pow(2, n - i - 1, p) * int(arr[n - i - 1]) * pow(11, i, p) for i in range(n))) % p)


mod = 1000000007
num = input()
n = len(num)
ans = [0 for i in range(n)]
ans[0] = int(num[0])
for i in range(1, n):
	ans[i] = (int(num[i]) * pow(2, i, mod) + 11 * ans[i - 1]) % mod
print(ans[n - 1])


s = input()
l = len(s)
mod = 1000000007
cnt = 1
sum = 0
for i in range(0, l):
	k = int(s[i])
	sum = (sum + sum * 10 + k * cnt) % mod
	cnt = (cnt << 1) % mod
print(sum)


def faster(ns):
	res = 0
	ponze = 1
	for c in reversed(ns):
		res = (2 * res + ponze * int(c)) % modo
		ponze = ponze * 11 % modo
	return res
modo = 10 ** 9 + 7
ns = input()
print(faster(ns))


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


s = map(int, input())
(res, k, p, pm1) = (next(s), 1, 1000000007, 1000000006)
for i in s:
	res = (res * 11 + (i << k) % p) % p
	k = (k + 1) % pm1
print(res)


s = input()
r = 0
m = 10 ** 9 + 7
for i in range(len(s)):
	r += int(s[i]) * pow(11, len(s) - i - 1, m) * pow(2, i, m) % m
print(r % m)


N = int(1000000000.0) + 7

def add(a, b):
	return (a + b) % N

def mult(a, b):
	return a * b % N

def total(n):
	t = 0
	for i in range(len(n) - 1, -1, -1):
		if i == len(n) - 1:
			contribution = 1
		else:
			contribution = mult(11, contribution)
		factor = mult(n[i], pow(2, i, N))
		t = add(t, mult(factor, contribution))
	return t
n = list(map(int, input()))
print(total(n))


n = int(input())
n1 = str(n)[::-1]
m = 10 ** 9 + 7
ans = 0
for i in range(len(n1)):
	ans += pow(2, len(n1) - 1 - i, m) * int(n1[i]) * pow(11, i, m) % m
print(ans % m)


m = 10 ** 9 + 7
s = input()
l = len(s)
sm = 0
for i in range(l):
	k = l - i - 1
	sm += int(s[i]) * (pow(2, i, m) * pow(11, k, m)) % m % m
print(sm % m)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


num = input()
n = len(num)
sumt = 0
d = 1000000007
for i in range(n):
	sumt = (sumt + int(num[i]) * pow(11, n - 1 - i, d) * pow(2, i, d) % d) % d
print(sumt)


n = list(input())
mod = 10 ** 9 + 7
r = [int(x) for x in n]
ans = 0
p2 = 1
for x in r:
	ans = (ans * 11 + x * p2) % mod
	p2 = p2 * 2 % mod
print(ans)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m
N = input()
d = len(N)
modulus = pow(10, 9) + 7
eleven_jay = 1
two_minus_jay = 1
two_inverse = pow_mod(2, modulus - 2, modulus)
total = ord(N[d - 1]) - ord('0')
for j in range(1, d):
	eleven_jay *= 11
	eleven_jay %= modulus
	two_minus_jay *= two_inverse
	two_minus_jay %= modulus
	total += (ord(N[d - 1 - j]) - ord('0')) * eleven_jay * two_minus_jay
	total %= modulus
total *= pow_mod(2, d - 1, modulus)
total %= modulus
print(total)


S = input()
N = len(S)
T = 0
for k in range(N):
	d = int(S[k])
	T = (T + pow(2, k, 1000000007) * pow(11, N - k - 1, 1000000007) * d) % 1000000007
print(T)


MOD = 1000000007
n = list(map(int, list(input().strip())))
r = 0
k = 0
for (_, digit) in enumerate(n):
	r += (10 * r + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(r % MOD)


def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))


P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


MOD = 1000000007
n = list(map(int, list(input().strip())))
r = 0
k = 0
for (_, digit) in enumerate(n):
	r += (10 * r + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(r % MOD)


M = 10 ** 9 + 7
N = input().strip()
S = 0
P = 1
for i in range(len(N)):
	S = (S * 11 + P * int(N[i])) % M
	P = (P << 1) % M
print(S)


s = input().strip()
n = len(s)
p = 10 ** 9 + 7
ans = 0
for i in range(n):
	ans += pow(2, i, p) * pow(11, n - i - 1, p) * int(s[i])
	ans %= p
print(ans)


import os
import sys

def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))


a = input()
n = len(a)
(i, mysum) = (0, 0)
for i in range(n):
	mysum = (mysum + pow(2, i, 1000000007) * pow(11, n - i - 1, 1000000007) * int(a[i])) % 1000000007
print(mysum)


def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))


import math
import sys
MOD = 1000000007

def solve(s):
	lsum = 0
	pow2 = 1
	for (i, ch) in enumerate(s):
		digit = int(ch)
		lsum = (lsum * 11 + digit * pow2) % MOD
		pow2 = (pow2 + pow2) % MOD
	return lsum

def hr_main(ifile=sys.stdin, ofile=sys.stdout):
	s = ifile.readline().strip()
	result = solve(s)
	print(result, file=ofile)
hr_main()


(s, b, m) = (input(), 0, 10 ** 9 + 7)
for x in range(len(s)):
	b += int(s[x]) * pow(2, x, m) * pow(11, len(s) - x - 1, m)
print(b % m)


l = list(map(int, list(input())))
size = len(l)
p = 10 ** 9 + 7
ans = 0
for i in range(size):
	ans += pow(2, i, p) * pow(11, size - 1 - i, p) * l[i] % p
print(ans % p)


def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))


n = str(input())
l = len(n) - 1
res = int(n[0])
m = 10 ** 9 + 7
for i in range(l):
	res = (res * 11 % m + pow(2, i + 1, m) * int(n[i + 1]) % m) % m
print(res)


P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


import sys
MOD = 1000000007
N = list(map(int, list(sys.stdin.readline().strip())))
total = 0
k = 0
for (i, digit) in enumerate(N):
	total += (10 * total + (k + 1) * digit) % MOD
	k = (2 * k + 1) % MOD
print(total % MOD)


def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))


P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


P = 10 ** 9 + 7
s = [ord(c) - ord('0') for c in input()]
ret = 0
for (i, x) in enumerate(s):
	ret = (11 * ret + x * pow(2, i, P)) % P
print(ret)


mod = int(1000000000.0 + 7)
n = input().strip()
(sum, cnt) = (0, 0)
for d in n:
	d = int(d)
	sum = (sum + sum * 10 + (cnt + 1) * d) % mod
	cnt = (cnt + cnt + 1) % mod
print(sum)


def manasa_simpliste(n):
	d = []
	for i in n:
		d.append(int(i))
	result = 0
	for i in range(1, 2 ** len(d)):
		x = 0
		j = i
		k = 0
		while j != 0:
			(j, r) = divmod(j, 2)
			if r == 1:
				x = x * 10 + d[k]
			k += 1
		result += x
	return result

def powmod(x, k, MOD):
	p = 1
	if k == 0:
		return p
	if k == 1:
		return x
	while k != 0:
		if k % 2 == 1:
			p = p * x % MOD
		x = x * x % MOD
		k //= 2
	return p

def manasa(n):
	MOD = 1000000007
	result = 0
	m = len(n) - 1
	q = 1
	for c in n[::-1]:
		c = int(c)
		p = powmod(2, m, MOD)
		x = c * p % MOD
		result = (result + x * q) % MOD
		m -= 1
		q = q * 11 % MOD
	return result % MOD
assert manasa('111') == 147
assert manasa('123') == 177
print(manasa(input()))