题目描述
小 C 最近迷上了一款游戏。现在，在游戏中，小 C 有一个英雄，生命值为x；敌人也有一个英雄，生命值为 y。除此以外，还有 k 个士兵，生命值分别为a1、a2、……、ak。现在小 C 打算使用一个叫做“燃烧权杖”的技能。“燃烧权杖”会每次等概率随机选择一个活着的角色（英雄或士兵），扣减其 10 点生命值，然后如果该角色的生命值小于或等于 0，则该角色死亡，不会再被“燃烧权杖”选中。“燃烧权杖”会重复做上述操作，直至任意一名英雄死亡。小 C 想知道使用“燃烧权杖”后敌方英雄死亡（即，小 C 的英雄存活）的概率。为了避免精度误差，你只需要输出答案模一个质数 p 的结果，具体见输出格式。
输入格式
输入包含多组数据。
输入第一行包含一个正整数 T，表示数据组数。
接下来 T 组，每组数据第一行包含四个非负整数 x、y、p、k，分别表示小C 的英雄的生命值、敌方英雄的生命值，模数和士兵个数。
第二行包含 k 个正整数 a1、a2、……、ak，分别表示每个士兵的生命值。
输出格式
对于每组数据，输出一行一个非负整数，表示答案模质数 p 的余数。
可以证明，答案一定为有理数。设答案为 a/b（a 和 b 为互质的正整数），你输出的数为 x，则你需要保证 a 与 bx 模 p 同余；也即，x = (a · b 1) mod p，其中 b 1 表示 b 模 p 的逆元， mod 为取模运算。
可以证明，答案一定为有理数。设答案为 a/b（a 和 b 为互质的正整数），你输出的数为 x，则你需要保证 a 与 bx 模 p 同余；也即，x = (a · b 1) mod p，其中 b 1 表示 b 模 p 的逆元， mod 为取模运算。
样例输入
6 1 10 101 0 100 1 101 0 50 30 4903 2 1 1 987 654 233 1 321 1000000000 999999999 233 3 1 2 3 1000000000 999999999 3 3 1 2 3
样例输出
51 37 1035 118 117 2
提示
【样例说明】
对于第一组数据，所求概率即为“燃烧权杖”第一次就扣减敌方英雄 10 点
生命值的概率，即 1/2。2 × 51 模 101 余 1。
对于第二组数据，答案为 1023/1024，1024 × 37 与 1023 模 101 同余。
对于第三组数据，答案为 99/128。
【评测用例规模与约定】
对于第一组数据，所求概率即为“燃烧权杖”第一次就扣减敌方英雄 10 点
生命值的概率，即 1/2。2 × 51 模 101 余 1。
对于第二组数据，答案为 1023/1024，1024 × 37 与 1023 模 101 同余。
对于第三组数据，答案为 99/128。
【评测用例规模与约定】
对于 10% 的评测用例，x, y, a1, · · · , ak ≤ 10。
对于 20% 的评测用例，x, y, a1, · · · , ak ≤ 100。
对于 50% 的评测用例，x, y, a1, · · · , ak ≤ 1000。
另有 10% 的评测用例，p = 3。
另有 20% 的评测用例，p ≤ 100。
对于全部评测用例，1 ≤ x, y, a1, · · · , ak ≤ 109，3 ≤ p ≤ 10000 且 p 为质数，0 ≤ k ≤ 10。