← 返回题目列表

AtCoder · kupc2014_l

L. 电源号码

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

幂数的集合定义如下。

  • 1 是一个幂数 如果
  • x 是幂 2^x, 3^x, 5^x, 7^x也是一个幂数。
  • 只有从上述两个条件可以确定为幂的数才是幂。 由
2 或 上面写着字符 3 或 上面写着字符 5 或 上面写着字符 7 组成的序列 给出了 b_1,...,b_N 。 {b_1}\^{b_2}\^...\^{b_N} 小于的幂数 除以 10^{9}+7 求余数。

(注) {b_1}\^{b_2}\^...\^{b_N} 是指通过优先考虑右侧的权力计算出的值。例如, 2\^3\^2=2\^9=512 。

入力形式

测试用例按以下格式给出。

N
b_1
b_2
…
b_N

出力形式

输出所需的答案。

制約

  • 1 \leq N \leq 1000
  • b_i∈\{2,3,5,7\}

针对该问题的判断设置了一组50分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。

  • 1 ≤ N ≤ 4

入出力例

入力例1

2
3
2

出力例1

7

3^2=9 较小的功率是 有七个 1,2,3,4,5,7,8 。 输出除以

入力例2

3
2
7
5

出力例2

100

入力例2

32
2
2
2
2
3
3
3
3
5
5
5
5
7
7
7
7
2
2
2
2
3
3
3
3
5
5
5
5
7
7
7
7

出力例2

223914000

10^9+7 后的余数。