Andrew and Eugene are playing a game. Initially, Andrew has string s, consisting of digits. Eugene sends Andrew multiple queries of type "d_{i} → t_{i}", that means "replace all digits d_{i} in string s with substrings equal to t_{i}". For example, if s = 123123, then query "2 → 00" transforms s to 10031003, and query "3 → " ("replace 3 by an empty string") transforms it to s = 1212. After all the queries Eugene asks Andrew to find the remainder after division of number with decimal representation equal to s by 1000000007 (10^9 + 7). When you represent s as a decimal number, please ignore the leading zeroes; also if s is an empty string, then it's assumed that the number equals to zero.

Andrew got tired of processing Eugene's requests manually and he asked you to write a program for that. Help him!


-----Input-----

The first line contains string s (1 ≤ |s| ≤ 10^5), consisting of digits — the string before processing all the requests.

The second line contains a single integer n (0 ≤ n ≤ 10^5) — the number of queries.

The next n lines contain the descriptions of the queries. The i-th query is described by string "d_{i}->t_{i}", where d_{i} is exactly one digit (from 0 to 9), t_{i} is a string consisting of digits (t_{i} can be an empty string). The sum of lengths of t_{i} for all queries doesn't exceed 10^5. The queries are written in the order in which they need to be performed.


-----Output-----

Print a single integer — remainder of division of the resulting number by 1000000007 (10^9 + 7).


-----Examples-----
Input
123123
1
2->00

Output
10031003

Input
123123
1
3->

Output
1212

Input
222
2
2->0
0->7

Output
777

Input
1000000008
0

Output
1



-----Note-----

Note that the leading zeroes are not removed from string s after the replacement (you can see it in the third sample).

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
MOD = 1000000007
(st, n, t, mp) = (input(), int(input()), [], {})
t.append(['', st])
for i in range(10):
	mp[str(i)] = (10, i)
for i in range(n):
	t.append(input().split('->'))
for i in range(n, -1, -1):
	(a, b) = (1, 0)
	for j in t[i][1]:
		(a, b) = (a * mp[j][0] % MOD, (b * mp[j][0] + mp[j][1]) % MOD)
	mp[t[i][0]] = (a, b)
print(mp[''][1])


MOD = 10 ** 9 + 7
s = input()
n = int(input())
qs = [['', s]] + [input().split('->') for i in range(n)]
ds = {}
for i in range(10):
	ds[str(i)] = (10, i)
for i in range(n, -1, -1):
	out = 0
	mul = 1
	for d in qs[i][1]:
		out = (out * ds[d][0] + ds[d][1]) % MOD
		mul = mul * ds[d][0] % MOD
	ds[qs[i][0]] = (mul, out)
print(ds[''][1])


def main():
	s = input()
	n = int(input())
	M = 1000000007
	a = {str(s): [10, s] for s in range(10)}
	d = [['_', s]] + [input().split('->') for _ in range(n)]
	for (di, ti) in reversed(d):
		_p = 1
		_v = 0
		for c in ti:
			_v = (_v * a[c][0] + a[c][1]) % M
			_p = _p * a[c][0] % M
		a[di] = [_p, _v]
	print(a['_'][1])

def __starting_point():
	main()
__starting_point()


m = 1000000007
p = [(0, input())] + [input().split('->') for i in range(int(input()))]
s = [(10, i) for i in range(10)]
for (d, t) in p[::-1]:
	(a, b) = (1, 0)
	for q in t:
		(x, y) = s[int(q)]
		(a, b) = (a * x % m, (b * x + y) % m)
	s[int(d)] = (a, b)
print(s[0][1])


mod = pow(10, 9) + 7

def sub_and_eval(n):
	if n == '':
		return 0
	ans = v[int(n[0])]
	for i in range(1, len(n)):
		ans = (d[int(n[i])] * ans + v[int(n[i])]) % mod
	return ans

def prod_d(n):
	ans = 1
	for e in n:
		ans = ans * d[int(e)] % mod
	return ans
s = input()
v = {i: i for i in range(10)}
d = {i: 10 for i in range(10)}
k = int(input())
arr = []
for _ in range(k):
	(a, b) = input().split('->')
	arr.append((a, b))
for (a, b) in reversed(arr):
	v[int(a)] = sub_and_eval(b)
	d[int(a)] = prod_d(b)
print(sub_and_eval(s))