Description

给定n个正整数a1,a2,…,an，求 的值（答案模10^9+7）。

Format

Input

第一行一个正整数n。

接下来n行，每行一个正整数，分别为a1,a2,…,an。

Output

仅一行答案。

Samples

3
6
10
15

1595

Limitation

1<=n<=10^5，1<=ai<=10^7。共3组数据。