UOJ Logo FLYIOI UOJ

FLYIOI

#33. 投篮大赛(shoot)

故事背景

这该死的有奖竞答节目居然还对选手的身体素质有极高要求,你让yuyan怎么活。

题目描述

考官宣布了这次选拔的评分规则:有n个篮球,每个球上被贴着一个正整数。有m个篮框,每个篮板上有一个计分器,显示一个整数,初值为1。选手被要求将每个篮球投向任意一个篮筐。如果将一个写有整数x的篮球投进了某个计分器显示为y的篮,则该篮板上的计分器显示值将从y变成y×x。最后裁判会将所有被投入过的篮筐(若某篮筐未被投入过,则其分数不算入总分)上的记分器的值加起来,作为选手的得分。为了这次比赛,yuyan已经把自己炼成了百发百中的神投手,剩下要做的就是争取拿到最高的分数。

输入

第一行两个整数n(n<=100000),m(m<=100000)。
接下来n行每行一个正整数ai(1<=ai<=1000),表示该篮球的权值。

输出

第一行一个整数,表示yuyan能拿到的最高分数,由于这个数太大,所以请把结果对1000000007取模。

样例输入

5 5
2
3
4
5
6

样例输出

720

样例解释

Yuyan把所有球都投进了一个框框里,所以2*3*4*5*6=720。

数据范围

对于20%的数据,n<=5 , m<=5 , 1<=ai<=10
对于100%的数据,n<=100000 , m<=100000 , 1<=ai<=1000