No submission language available for this problem.

Background

Special for beginners, ^_^

Description

郑老师挑战关小山，他对关小山准备了亿个数字相乘的题。郑老师认为自己的代码天下第一让同学们很不爽，于是同学们想让你帮关小山写一个代码打败老师，若胜利能够被奖励 100 分。

为了这点分，你需要对一序列数据进行处理。若第一个数为 1，则需要将序列之后的所有数字相乘，并给出结果。若第一个数为 0，则需要将序列之后的所有数字相加，给出最终结果的负值。

注意由于乘法的结果过大，因此若为乘法计算，请将最终的结果模上 1000000007 。

Format

Input

第一行一个整数 n，表示将会输入 n 个整数

第二行是一个有 n 个整数的序列 $a_i$

Output

输出处理后的结果

Samples

3
1 2 1

2

Limitation

$1<=n<=10^6$

$0 < a_i <= 10^6$

1s, 1024KiB for each test case.