C. 水母与永恒紫罗兰

题目描述

水母面前有 $n$ 只怪物，编号从 $1$ 到 $n$。第 $i$ 只怪物的生命值为 $h_i$。

水母不想杀死它们，但她希望这些怪物不会对她构成威胁。因此，她希望将所有怪物的生命值都减少到恰好 $1$。

现在，水母手持"以泪淬炼之剑"，将进行 $m$ 轮攻击。每一轮的过程如下：

• "以泪淬炼之剑"以概率 $p$ 闪耀。
• 水母可以选择是否攻击：
  • 如果水母不攻击，则什么都不会发生。
  • 如果水母选择攻击，且剑闪耀，则所有怪物的生命值减少 $1$。
  • 如果水母选择攻击，但剑未闪耀，则水母可以选择其中一只怪物，将其生命值减少 $1$。

请注意：在水母决定是否攻击之前，她会知道剑是否闪耀。此外，当剑闪耀时，水母只能攻击所有怪物，不能只攻击单个怪物。

现在，水母想知道，如果她在战斗过程中以最优策略进行决策，她达成目标的概率是多少。

输入格式

每个测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $p'$（$1 \le n \le 20$，$1 \le m \le 4000$，$0 \le p' \le 100$）——怪物的数量、攻击轮数，以及一个表示概率 $p = \frac{p'}{100}$ 的整数。

每个测试用例的第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 400$）——怪物的生命值。

保证所有测试用例的 $n$ 之和不超过 $100$。

输出格式

对于每个测试用例，输出一个实数，表示水母达成目标的概率。

如果绝对误差或相对误差不超过 $10^{-6}$，则认为答案正确。

形式化地说，设你的答案为 $a$，标准答案为 $b$。如果 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$，则答案被接受。

示例

输入

4
2 2 10
2 2
5 5 20
2 2 2 2 2
6 20 50
1 1 4 5 1 4
9 50 33
9 9 8 2 4 4 3 5 3

输出

0.910000
0.672320
0.588099
0.931474

样例解释

第一个测试用例：水母在第一轮无论剑是否闪耀都会攻击。

• 如果第一轮剑闪耀，攻击后水母即可达成目标。
• 如果第一轮剑未闪耀，她会在第一轮攻击怪物 $1$。在第二轮：
  • 如果剑闪耀，由于怪物 $1$ 在第一轮已被攻击，她无法达成目标。
  • 如果剑未闪耀，水母可以攻击怪物 $2$，从而达成目标。

因此，水母能达成目标的概率为 $10\% + (90\% \times 90\%) = 91\%$。

第二个测试用例：水母只在剑闪耀的轮次攻击。可以观察到，水母无法达成目标的唯一情况是剑在全部 $5$ 轮中从未闪耀。因此，水母能达成目标的概率为 $100\% - (80\%)^5 = 67.232\%$。