#P6876. b

    ID: 6707 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-二项分布第二类 Stirling 数二项式定理指示变量期望线性性独立随机变量乘积期望下降阶乘基底运算阶乘逆元预处理模逆元快速幂

b

题目描述

第一只袋子中存放若干正整数,第二只袋子也存放若干正整数。各从这两只袋子里等概率且独立地抽取一个数,记为 n,mn,m。准备 nn 个新袋子,把 mm 个球各自独立、等概率地放进这 nn 个袋子之一。然后独立且等概率地选一个新袋子,令 XX 是其中的球数。

对每个询问 kk,计算中心矩。先对固定的 n,mn,m 计算 E⁡[(X−m/n)k∣n,m]\operatorname E[(X-m/n)^k\mid n,m],再对抽到的 n,mn,m 取期望。

输入格式

第一行三个正整数 Nn,Nm,NkN_n,N_m,N_k,分别是第一只袋子的整数种类数、第二只袋子的整数种类数和询问数。

接下来 NnN_n 行,每行两个正整数 ni,cin_i,c_i,表示第一只袋子里有 cic_i 个 nin_i。接下来 NmN_m 行,每行两个正整数 mi,dim_i,d_i,表示第二只袋子里有 did_i 个 mim_i。

接下来 NkN_k 行,每行一个正整数 kk。

输出格式

每个询问输出一行。若答案为最简分数 a/ba/b,输出 ab−1 mod (109+7)a b^{-1}\bmod(10^9+7) 的最小非负代表元。答案为零时输出 0。

样例

1 1 2
3 1
2 1
2
3
444444448
481481485
2 2 2
3 2
2 1
3 2
2 1
2
3
172839508
650205766

第一组的二阶中心矩为 4/94/9,第二组的二阶中心矩为 50/8150/81。

数据范围

1≤ni,mi≤1091\le n_i,m_i\le10^9,1≤Nn≤50001\le N_n\le5000,1≤Nm,k,ci,di≤20001\le N_m,k,c_i,d_i\le2000,1≤Nk≤2001\le N_k\le200。各档测试点范围见原 PDF 第 2–3 页。

By 杨景钦。原题面 PDF