{"raw_statement":[{"iden":"problem statement","content":"There are $N$ children, numbered $1, 2, \\ldots, N$.\nThey have decided to share $K$ candies among themselves. Here, for each $i$ ($1 \\leq i \\leq N$), Child $i$ must receive between $0$ and $a_i$ candies (inclusive). Also, no candies should be left over.\nFind the number of ways for them to share candies, modulo $10^9 + 7$. Here, two ways are said to be different when there exists a child who receives a different number of candies."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 100$\n*   $0 \\leq K \\leq 10^5$\n*   $0 \\leq a_i \\leq K$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$a_1$ $a_2$ $\\ldots$ $a_N$"},{"iden":"sample input 1","content":"3 4\n1 2 3"},{"iden":"sample output 1","content":"5\n\nThere are five ways for the children to share candies, as follows:\n\n*   $(0, 1, 3)$\n*   $(0, 2, 2)$\n*   $(1, 0, 3)$\n*   $(1, 1, 2)$\n*   $(1, 2, 1)$\n\nHere, in each sequence, the $i$\\-th element represents the number of candies that Child $i$ receives."},{"iden":"sample input 2","content":"1 10\n9"},{"iden":"sample output 2","content":"0\n\nThere may be no ways for the children to share candies."},{"iden":"sample input 3","content":"2 0\n0 0"},{"iden":"sample output 3","content":"1\n\nThere is one way for the children to share candies, as follows:\n\n*   $(0, 0)$"},{"iden":"sample input 4","content":"4 100000\n100000 100000 100000 100000"},{"iden":"sample output 4","content":"665683269\n\nBe sure to print the answer modulo $10^9 + 7$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}