Substitutes in Number

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⁹ + 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⁵), consisting of digits — the string before processing all the requests.

The second line contains a single integer n (0 ≤ n ≤ 10⁵) — 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⁵. 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⁹ + 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).

Solution:

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

using namespace std;

const int md = 1000000007;

inline void add(int &a, int b) {
a += b;
if (a >= md) {
a -= md;
}
}

inline int mul(int a, int b) {
return (long long)a * b % md;
}

const int N = 400010;

char s[N];

char foo[N];

char dig[N];
vector <char> to[N];

int pw[N], val[N];

int main() {
scanf("%s", s);
int n = strlen(s);
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
    scanf("%s", foo);
    dig[i] = foo[0];
    to[i].clear();
    for (int j = 3; foo[j]; j++) {
      to[i].push_back(foo[j]);
    }
  }
  for (int d = 0; d < 10; d++) {
    pw[d] = 10;
    val[d] = d;
  }
  for (int i = m - 1; i >= 0; i--) {
int d = dig[i] - '0';
int n_pw = 1;
int n_val = 0;
int sz = to[i].size();
for (int j = 0; j < sz; j++) {
      int t = to[i][j] - '0';
      n_val = mul(n_val, pw[t]);
      add(n_val, val[t]);
      n_pw = mul(n_pw, pw[t]);
    }
    pw[d] = n_pw;
    val[d] = n_val;
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    int t = s[i] - '0';
    res = mul(res, pw[t]);
    add(res, val[t]);
  }
  printf("%d\n", res);
  return 0;
}