一天，猫猫路过了宝石店，店中有 nnn 块宝石，美丽度为整数 a1,...,ana_1,...,a_na1,...,an，神奇的是，如果把 ccc 个美丽度之和为 www 的宝石合并，可以合成一个美丽度为 cwccdot wcw 的新宝石，记 M=998244353M = 998244353M=998244353，可以证明答案可以表示成 pqfrac pqqp 其中 p≥0,q≥1,gcd(p,q)=1,qmodM=0p geq 0,qgeq 1,gcd(p,q) = 1,qbmod Mnot=0p≥0,q≥1,gcd(p,q)=1,qmodM=0，故你只要输出 pq1modMpcdot q^{-1}bmod Mpq1modM 即可，此处 q1q^{-1}q1 表示 qqq 在模 MMM 意义下的逆元，即 qq1≡1q q^{-1}equiv 1pmod {M}qq1≡1，例如本题数字 222 在模 MMM 意义下的逆元是 M+12frac{M+1}22M+1。
一天，猫猫路过了宝石店。 店中有 nnn 块宝石，美丽度为整数 a1,...,ana_1,...,a_na1,...,an。 神奇的是，如果把 ccc 个美丽度之和为 www 的宝石合并，可以合成一个美丽度为 c⋅wccdot wc⋅w 的新宝石。 猫猫想知道，如果她随机选一些宝石 (共 2n2^n2n 种选法)，每个宝石以 0.50.50.5 的概率被选中，然后把所有选中的宝石合并，获得的新宝石美丽度的期望值是多少。如果没有任何宝石被选中，我们认为新宝石的美丽度为 000。 猫猫非常贪心，她想对于每个 i=1,2,...,ni=1,2,...,ni=1,2,...,n，都询问一下假设只有前 iii 块宝石，随机选一些宝石合并，新宝石美丽度的期望是多少。 离散型随机变量 XXX 的期望定义如下：设 XXX 所有可能的取值是 v1,v2,...,vmv_1,v_2,...,v_mv1,v2,...,vm，概率对应为 p1,p2,...,pmp_1,p_2,...,p_mp1,p2,...,pm (满足 ∑pi=1sum p_i = 1∑pi=1)，则期望 E(X)=∑i=1mpiviE(X) = sum_{i = 1}^m p_i v_iE(X)=∑i=1mpivi。 记 M=998244353M = 998244353M=998244353。可以证明答案可以表示成 pqfrac pqqp 其中 p≥0,q≥1,gcd(p,q)=1,q mod M≠0p geq 0,qgeq 1,gcd(p,q) = 1,qbmod Mnot=0p≥0,q≥1,gcd(p,q)=1,qmodM=0，故你只要输出 p⋅q−1 mod Mpcdot q^{-1}bmod Mp⋅q−1modM 即可。此处 q−1q^{-1}q−1 表示 qqq 在模 MMM 意义下的逆元，即 qq−1≡1(modM)q q^{-1}equiv 1pmod {M}qq−1≡1(modM)，例如本题数字 222 在模 MMM 意义下的逆元是 M+12frac{M+1}22M+1。
