2023 年上海市大学生程序设计竞赛 - 六月赛

E. 第k大

单点时限: 1.5 sec

内存限制: 256 MB

有 $n$ 个相互独立随机数生成器,第 $i$ 个生成器按均匀分布随机生成 $[0, a_i]$ 内的任意实数。

现在需要求解这 $n$ 随机数中排名第 $k$ 大数的期望值,答案对 $10^9+7$ 取模。

输入格式

第一行 一个整数,$n$

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$

输出格式

输出一行, $n$ 个整数,第 $i$ 个表示第 $i$ 大数的期望值对 $10^9+7$ 取模的结果(可以证明该期望值是有理数),用一个空格隔开。

样例

Input
3
4 4 4
Output
3 2 1
Input
3
1 2 3
Output
736111118 888888896 375000003

提示

$n\le 300$

$1\le a_i\le 10^9$

样例二的期望值分别是 $53/72, 8/9, 3/8$