CF464C 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^{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!

The first line contains string $ s $ ( $ 1

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

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