小红的双排列期望（hard）

题号：NC297618
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为问题的困难版本，两题的唯一区别在于操作失败的代价。

$\hspace{15pt}$ 小红拿到了一个长度为 $2 \times n$ 的数组 $\{a_1,a_2,\dots,a_{2\times n}\}$ ，初始所有元素都是 $0$ ，她可以进行任意次以下操作：
$\hspace{23pt}\bullet\,$ 尝试使 $a_i$ 加 $1$ 。该操作有 $b_i \%$ 的概率成功。若成功，则 $a_i$ 加 $1$ ；若失败，如果 $a_i$ 大于 $0$ 则会减 $1$ （等于 $0$ 则无变化）。
$\hspace{15pt}$ 小红希望最终 $a$ 变成一个双排列。她希望最小化操作次数，请你求出小红最优策略下，最终操作次数的期望。答案对 $10^9+7$ 取模。

【名词解释】
$\hspace{15pt}$ 双排列：长度为 $2\times n$ 的双排列为两个长度为 $n$ 的排列打乱顺序后得到的数组。
$\hspace{15pt}$ 排列：长度为 $n$ 的排列是由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

【提示】
$\hspace{15pt}$ 本题中，如果您需要使用到除法的取模，即计算 $\left(p\times q^{-1} \bmod M\right)$ 时， $q^{-1}$ 需要使用公式 $\left(q^{M-2} \bmod M \right)$ 得到。例如，计算 $\tfrac{5}{4} \bmod M$ ：

$\begin{array}{rll} 4^{-1} & = & \left(4^{M-2} \bmod M\right) \\ & = & 250\,000\,002 \\ \hline \left(\tfrac{5}{4} \bmod M\right) & = & 5 \times4^{-1} \bmod M \\ & = & 5 \times 250\,000\,002 \bmod M \\ & = & 250\,000\,003 \end{array}$

输入描述:

第一行输入一个正整数 。
第二行输入  个整数 ，代表每个元素操作成功的概率百分比。

输出描述:

在一行上输出一个整数，代表最终期望对  取模的答案。

示例1

输入

复制

1
50 50

输出

复制

说明

在这个样例中，最终期望操作次数为  次。