Alice 和 Bob 正在玩游戏。有 $$$n$$$ 球,其中 $$$k$$$ 是特殊的。每个球都有一个与之相关的值。
玩家轮流进行游戏。在每个回合中,玩家随机选择一个球,并将球的值添加到他们的分数中,即游戏开始时的 $$$0$$$。选定的球将从游戏中移除。如果球是特殊的,则在至少还剩下一个球的情况下,由同一位球员进行下一回合。如果选择的球不特殊,则轮到下一个玩家进行。
他们玩这个游戏,直到游戏中没有球为止。爱丽丝先玩。
求游戏结束时双方玩家的预期得分以 $$$10^9+7$$$ 为模。
正式地,令 $$$M = 10^9+7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
输入
有多个测试用例。输入的第一行包含一个整数$$$t$$$,即测试用例的数量($$$1 \le t \le 2 \cdot 10^5$$$)。
每个测试用例描述都换行。测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$,按各自的顺序用空格分隔 ($$$1 \le k \le n \le 4 \cdot 10^5$$$)。
测试用例的第二行包含 $$$n$$$ 整数:$$$v_1, v_2, \ldots, v_n$$$,每个球的值以空格分隔。第一个 $$$k$$$ 球很特殊($$$1 \le v_i \le 10^7$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
在新行中输出每个测试用例的两个整数,Alice 的预期分数和 Bob 的预期分数模 $$$10^9+7$$$。
示例
输入 #1
1 5 2 10 20 5 15 25
输出 #1
45 30
输入 #2
5 1 1 732507 2 2 5817860 5398510 5 1 2122894 4951549 2750585 7821535 3214167 8 4 1405323 5069867 6883092 6972029 328406 2478975 7628890 9973340 4 2 9662050 3566134 3996473 9872255
输出 #2
732507 0 11216370 0 810642660 210218077 722402997 318336932 349086489 678010430
输入 #3
5 3 3 1095611 8219204 7773462 2 1 8176490 2774103 3 1 9178636 5138057 3367761 12 9 7597698 6843019 2298534 1522386 4969588 1340345 3967362 9152890 6689668 9986080 4745473 7407325 10 5 6986368 2397882 5804127 6980694 3740836 3215836 5195724 3179261 4136769 4544231
输出 #3
17088277 0 6862348 4088245 677038671 340645790 36949997 29570371 725118051 321063684
注意
在第一个测试用例中,游戏结束时 Alice 的预期得分为 $$$45$$$,Bob 的预期得分为 $$$30$$$。