{"problem":{"name":"Knapsack for All Subsets","description":{"content":"Given are a sequence of $N$ positive integers $A_1$, $A_2$, $\\ldots$, $A_N$ and another positive integer $S$.   For a non-empty subset $T$ of the set ${1, 2, \\ldots , N }$, let us define $f(T)$ as fol","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc169_f"},"statements":[{"statement_type":"Markdown","content":"Given are a sequence of $N$ positive integers $A_1$, $A_2$, $\\ldots$, $A_N$ and another positive integer $S$.  \nFor a non-empty subset $T$ of the set ${1, 2, \\ldots , N }$, let us define $f(T)$ as follows:  \n\n*   $f(T)$ is the number of different non-empty subsets ${x_1, x_2, \\ldots , x_k }$ of $T$ such that $A_{x_1}+A_{x_2}+\\cdots +A_{x_k} = S$.\n\nFind the sum of $f(T)$ over all $2^N-1$ subsets $T$ of ${1, 2, \\ldots , N }$. Since the sum can be enormous, print it modulo $998244353$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 3000$\n*   $1 \\leq S \\leq 3000$\n*   $1 \\leq A_i \\leq 3000$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $S$\n$A_1$ $A_2$ $...$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc169_f","tags":[],"sample_group":[["3 4\n2 2 4","6\n\nFor each $T$, the value of $f(T)$ is shown below. The sum of these values is $6$.\n\n*   $f({1}) = 0$\n*   $f({2}) = 0$\n*   $f({3}) = 1$ (One subset ${3}$ satisfies the condition.)\n*   $f({1, 2}) = 1$ (${1, 2}$)\n*   $f({2, 3}) = 1$ (${3}$)\n*   $f({1, 3}) = 1$ (${3}$)\n*   $f({1, 2, 3}) = 2$ (${1, 2}, {3}$)"],["5 8\n9 9 9 9 9","0"],["10 10\n3 1 4 1 5 9 2 6 5 3","3296"]],"created_at":"2026-03-03 11:01:14"}}