{"problem":{"name":"Binomial Coefficient is Fun","description":{"content":"We have a sequence $A$ of $N$ non-negative integers. Compute the sum of $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i}$ over all sequences $B$ of $N$ non-negative integers whose sum is at most $M$, and print it","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc110_d"},"statements":[{"statement_type":"Markdown","content":"We have a sequence $A$ of $N$ non-negative integers.\nCompute the sum of $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i}$ over all sequences $B$ of $N$ non-negative integers whose sum is at most $M$, and print it modulo ($10^9 + 7$).\nHere, $\\dbinom{B_i}{A_i}$, the binomial coefficient, denotes the number of ways to choose $A_i$ objects from $B_i$ objects, and is $0$ when $B_i < A_i$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 2000$\n*   $1 \\leq M \\leq 10^9$\n*   $0 \\leq A_i \\leq 2000$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc110_d","tags":[],"sample_group":[["3 5\n1 2 1","8\n\nThere are four sequences $B$ such that $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i}$ is at least $1$:\n\n*   $B = {1, 2, 1}$, where $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i} = \\dbinom{1}{1} \\times \\dbinom{2}{2} \\times \\dbinom{1}{1} = 1$;\n    \n*   $B = {2, 2, 1}$, where $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i} = \\dbinom{2}{1} \\times \\dbinom{2}{2} \\times \\dbinom{1}{1} = 2$;\n    \n*   $B = {1, 3, 1}$, where $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i} = \\dbinom{1}{1} \\times \\dbinom{3}{2} \\times \\dbinom{1}{1} = 3$;\n    \n*   $B = {1, 2, 2}$, where $\\prod _{i = 1} ^N \\dbinom{B_i}{A_i} = \\dbinom{1}{1} \\times \\dbinom{2}{2} \\times \\dbinom{2}{1} = 2$.\n    \n\nThe sum of these is $1 + 2 + 3 + 2 = 8$."],["10 998244353\n31 41 59 26 53 58 97 93 23 84","642612171"]],"created_at":"2026-03-03 11:01:14"}}