← 返回题目列表

AtCoder · icpc2016autumn_j

J. 压缩公式

中文机器翻译题面 查看原题

问题陈述

您将获得一个压缩格式的简单但较长的公式。 压缩公式是由整数 $r_i$ 和字符串 $s_i$ 组成的 $N$ 对序列,仅由数字 ('0'-'9'), '+', '-', 和 '*'。 为了从压缩公式恢复原始公式,首先我们生成通过对所有 $i$ 重复 $s_i$ $r_i$ 次而获得的字符串,然后按照序列的顺序将它们连接起来。

您可以假设恢复的原始公式是格式良好的。 更准确地说,恢复后的公式满足以下 BNF:

<expression> := <term> | <expression> '+' <term> | <expression> '-' <term>
<term> := <number> | <term> * <number>
<number> := <digit> | <non-zero-digit> <number>
<digit> := '0' | <non-zero-digit>
<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

在这里,'+' 表示加法,'-' 表示减法,并且 '*' 表示整数乘法。

你的任务是编写一个程序,计算给定公式模 $1{,}000{,}000{,}007$ 的答案,其中 $x$ 模 $m$ 是一个非负整数 $r$,这样存在一个整数 $k$ 满足 $x = km + r$ 和 $0 \le r \lt m$;保证这样的$r$对于整数$x$和$m$是唯一确定的。


输入

输入由单个测试用例组成。

$N$
$r_1$ $s_1$
...
$r_N$ $s_N$

第一行包含一个整数 $N$ ($1 \le N \le 10^4$),它是压缩公式序列的长度。 以下 $N$ 行代表压缩公式的各个部分。 第 $i$ 行由整数 $r_i$ ($1 \le r_i \le 10^9$) 和字符串 $s_i$ ($1 \le |s_i| \le 10$) 组成,其中 $t_i$ 是 $s_i$ 的重复次数,$s_i$ 是原始公式的一段。 您可以假设通过串联重复片段从给定压缩公式恢复的原始公式满足问题陈述中的 BNF。

输出

打印给定压缩公式模 $1{,}000{,}000{,}007$ 的答案。



示例输入 1

1
5 1

样本输入 1 的输出

11111

示例输入 2

2
19 2*
1 2

样本输入 2 的输出

1048576

示例输入 3

2
1 1-10
10 01*2+1

样本输入 3 的输出

999999825

示例输入 4

4
3 12+45-12
4 12-3*2*1
5 12345678
3 11*23*45

样本输入 4 的输出

20008570