说明

传说每到12月24日晚上，有个神秘人会乘驾由9只驯鹿拉的雪橇在天上飞翔，挨家挨户地从烟囱进入屋里，然后偷偷把礼物放在孩子床头的袜子里。 

虽然没有人真的见过神秘人的样子，但是人们会装扮成他的样子来给孩子送上礼物。他通常被描述为一位老人，头戴红色帽子，因为总在圣诞节前夜出现派发礼物，所以习惯地称他为“圣诞老人”。

有$n$个小朋友，在12月24日晚每个人都收到了一个苹果，价值为 $a_i$

然而到了12月25日这一天，“圣诞老人”又出现了，圣诞老人把小朋友们召集在一起，同时定义一种排列的权值为将小朋友的苹果价值按照排列顺序拼接在一起。

例如：$a_1=1$,$a_2=20$,$a_3=300$ ,那么按照正序排列的权值为$120300$

现在要求出小朋友们所有排列方式的权值和，答案对$1e9+7$取模

对于长度为$n$的数组有$n!$种排列，例如对于$n=3$时,共有$6$种排列分别是：

$[a_1,a_2,a_3]$,$[a_1,a_3,a_2]$,$[a_2,a_1,a_3]$,$[a_2,a_3,a_1]$,$[a_3,a_1,a_2]$,$[a_3,a_2,a_1]$

输入格式

第一行一个正整数代表 $n$ ，表示有 $n$ 个小朋友。

第二行$n$个正整数 $a_1,a_2...a_n$, 分别代表小朋友的苹果价值。

输出格式

输出一行一个数代表答案

样例

3
1 20 3

12888

提示

【数据范围】

对于$30$%的数据：$2 ≤ n ≤ 9，1 ≤ a_i ≤  10$ 。

对于$100$%的数据保证：$2 ≤ n ≤ 200，1 ≤ a_i ≤  10^9$ 。