H. 憧憬成为巧克力

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

碳钾钨最近学习了变成食物的魔法,他想捉弄一下他的好朋友kuro

kuro发现自己的家里突然出现了块巧克力,每一块的美味值为,她的巧克力太多了,所以kuro决定玩一些神秘的游戏。

她先从巧克力堆里随机抽取一块巧克力,记下美味值为,放回后再抽取一块,记下美味值为,随后,她吃下美味值更大的那一块。

kuro想知道自己这么做所吃下的巧克力的期望值是多少,但她嫌弃这个问题太过简单,所以她想问你,对于所有的,对前块巧克力这么做的期望值为多少?

期望可以表示为一个分数(pq是互质的),你需要先找到一个整数,使得然后输出整数,使得,容易证明这样的整数是唯一的.

输入格式

第一行为一个整数,代表kuro的巧克力块数

第二行为个整数,代表每块巧克力的美味度

输出格式

输出行,每行是一个整数,代表期望。

样例

输入 #1

3
1 2 3

输出 #1

1
249561090
776412277

时,答案显然是1

时,答案为7/4

时,答案为22/9

数据范围与提示

kuro即将吃下碳钾钨身体的一部分前,碳钾钨变了回来,阻止了这场惨剧。