题目描述

每个盲盒里有且只有一个玩具，每种玩具的出现概率不一定相同。设共有 $n$ 种不同类型的玩具，若从一无所有开始，不断地打开盲盒，直到所有类型的玩具全部收集完整为止，请计算需要打开的盲盒数量的期望。

输入格式

第一行：单个整数表示 $n$ 第二行：$n$ 个整数 $p_1,p_2,\dots,p_n$ 表示各类型玩具出现的概率。记 $s=p_1+p_2+\dots+p_n$，则第 $i$ 种玩具出现的概率为 $p_i/s$

输出格式

设期望开盒次数为 $P/Q$，且 $P$ 和 $Q$ 互素，则输出一个整数，具体数值为

其中 $Q'$ 满足 $Q'Q\equiv 1\pmod {10007}$

2
1 1

3

样例解释 1

若只有两种类型的玩具，且出现概率相等，则开盲盒次数的期望为3（推理过程略）

3
1 1 1

5009

样例解释 2

期望为5.5，分数取模后得5009

3
2 2 1

4176

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 3$；
• 对于 $60\%$ 的数据，$1\leq n\leq 10$；
• 对于 $100\%$ 的数据，$1\leq n\leq 20$，
• $1\leq p_i\leq 100$。