{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   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$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"3 5\n1 2 1"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"10 998244353\n31 41 59 26 53 58 97 93 23 84"},{"iden":"sample output 2","content":"642612171"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}