第七回日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 464）F問題メモ

# noinspection PyUnresolvedReferences
# noinspection PyTypeChecker
@extend
class int:
    def bit_length(self) -> int:
        return 64 - abs(self).__ctlz__()

    def bit_count(self) -> int:
        return abs(self).__ctpop__()


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, x, aaa):
    MOD = 998244353

    if n == 1:
        return aaa[0] % MOD

    def get_partial_sum(aaa):
        n = len(aaa)
        total = [0] * (1 << n)
        for bitset in range(1, 1 << n):
            lsb = bitset & -bitset
            i = lsb.bit_length() - 1
            val = total[bitset ^ lsb] + aaa[i]
            total[bitset] = val
        return total

    facts, finvs = precompute_factorials(n, MOD)

    # 採用する集合 S を固定し、最後に Ak を採用して x 以上になるという組 (S,k) 1つにつき、そうなる確率（ i=|S| のみに依存）
    ppp = [0] * n
    for i in range(n):
        ppp[i] = facts[i] * facts[n - 1 - i] % MOD * finvs[n] % MOD

    n1 = n // 2
    n2 = n - n1

    nm = max(n1, n2)
    bit_counts = [0] * (1 << nm)
    for bitset in range(1, 1 << nm):
        lsb = bitset & -bitset
        bit_counts[bitset] = bit_counts[bitset ^ lsb] + 1

    bbb = aaa[:n1]
    ccc = aaa[n1:]
    lll = get_partial_sum(bbb)
    rrr = get_partial_sum(ccc)

    def get_expected(n1, n2, bbb, lll, rrr):
        rrr_by_size = [[] for _ in range(n2 + 1)]
        acc_by_size = []
        for bitset in range(1 << n2):
            rrr_by_size[bit_counts[bitset]].append(rrr[bitset])
        for size in range(n2 + 1):
            rbs = rrr_by_size[size]
            rbs.sort()
            acc = [0] * (len(rbs) + 1)
            for i in range(len(rbs)):
                acc[i + 1] = (acc[i] + rbs[i]) % MOD
            acc_by_size.append(acc)

        l_sums_full = [(lll[bitset], bitset, bit_counts[bitset]) for bitset in range(1 << n1)]
        l_sums_full.sort(reverse=True)

        result = 0
        for i in range(n1):
            a = bbb[i]
            bit = 1 << i
            l_sums = [item for item in l_sums_full if item[1] & bit == 0]
            for s2 in range(n2 + 1):
                rbs = rrr_by_size[s2]
                cbs = acc_by_size[s2]
                m = len(rbs)
                l = 0
                r = 0
                for wl, _, s1 in l_sums:
                    lo_lim = x - a - wl
                    hi_lim = x - wl
                    while r < m and rbs[r] < hi_lim:
                        r += 1
                    while l < m and rbs[l] < lo_lim:
                        l += 1
                    cnt = r - l
                    if cnt > 0:
                        tmp = (cbs[r] - cbs[l]) % MOD
                        tmp = (tmp + (a + wl) % MOD * cnt) % MOD
                        result += tmp * ppp[s1 + s2]
                        result %= MOD
        return result

    ans_l = get_expected(n1, n2, bbb, lll, rrr)
    ans_r = get_expected(n2, n1, ccc, rrr, lll)
    ans = (ans_l + ans_r) % MOD
    if ans < 0:
        ans += MOD
    return ans


n, x = list(map(int, input().split()))
aaa = list(map(int, input().split()))
ans = solve(n, x, aaa)
print(ans)