Description

给定一个集合，其有n个非负整数。每次任意从集合中拿出两个数，设其为$x$、$y$，再将$x*y+x+y$放回集合。

经过若干次操作后，集合中仅剩一个数。

求这个数的最小值是多少。

答案对10007取模。

Format

Input

第一行一个正整数$n$，描述集合大小。

第二行$n$个非负整数，表示集合里的数。

Output

输出一行，一个整数，表示经过若干次操作后，集合中剩下的数的最小值。

Samples

3
1 6 2

41

5
4 3 2 5 0

359

10
9 6 7 6 7 4 8 0 5 9

2772

Limitation

本题共有10个测试点，每个测试点10分。

设$m$为集合中数字的最大值。

对于40%的数据，$n\leq 10, m \leq 10$

对于另外30%的数据，$n\leq 5000, m \leq 500$

对于另外30%的数据，$n\leq 100000, m \leq 500$