#6132. 「2017 山东三轮集训 Day1」Flair

内存限制:233 MiB 时间限制:8000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

因版权问题,此题暂停评测,请等待重制数据后提交。

渐渐地,勇士和魔鬼发现,这种游戏可能要进行 10000! 回合,是根本不可能完成的。而在这期间,Lyra 凭借着超时代的排序能力早已完成了魔鬼所需的各项排序。于是魔鬼提议,勇士请魔鬼吃一顿饭,魔鬼便放他们走而用餐地点的决定权落到了 Lyra 手上。

作为首席排序使,Lyra 对数字有着超人类的敏感,她决定选择一家可以带来数学问题的餐馆。最终他们去了一家快餐店,这家快餐店有 n 种菜拍成一排,顾客依次走过 1 \sim n 号菜,并选择其中的一些加入自己的盘子,最终需要付的钱就是选择的菜的数量。

有趣的是,这个餐馆只接受 m 种纸币,第 i 种面值为 c_i ,且不设找零。此次前来营救 Lyra,勇士得到了滋滋国财政支持,他的钱可以认为是无限的(即每种面值的纸币都有无限个)。经过观察,Lyra 发现,魔鬼对食物并不挑剔,对于每种菜品,他都有 p\% 的概率把其加入盘子。

虽然勇士可以无限用钱,但是勇士不喜欢浪费,由于快餐店不设找零,付款的时候可能会有一血浪费掉的钱,即 m 种面值能组成的最少的大于等于饭钱的金额减去饭钱。Lyra 则更关心,浪费掉的金额的期望是多少。

显然这个期望乘以 100 ^ n 一定是个整数,你只需要输出期望乘以 100 ^ n 再对 10 ^ 9 + 7 取模后的结果。

输入格式

第一行一个正整数 T ,表示数据组数。
对于每组数据,第一行三个整数 n, m, p ,意义如题所述;第二行 m 个整数表示 c_i ,意义如题所述。

输出格式

对于每组数据输出一行一个整数表示期望乘以 100 ^ n 后对 10 ^ 9 + 7 取模后的结果。

样例

样例输入 1

3
1 1 50
2
2 4 100
4 5 6 7
2 2 50
1 3

样例输出 1

50
20000
0

样例输入 2

见「附加文件」中的 ex_flair2.in

样例输出 2

见「附加文件」中的 ex_flair2.out

数据范围与提示

对于全部数据, T \leq 10; 1 \leq n \leq 10 ^ 9; 1 \leq m \leq 100; 0 \leq p \leq 100; 1 \leq c_i \leq 10 ^ 4; c_i c_J \leq 10000(i \neq j); c_i \neq c_j(i \neq j)

子任务 1(10 分) n \leq 10 ^ 5
子任务 2(25 分) c_i \leq 500; c_i c_j \leq 500(i \neq j)
子任务 3(25 分) m = 1
子任务 4(15 分) T \leq 3
子任务 5(25 分) T \leq 10