{"problem":{"name":"Candies","description":{"content":"There are $N$ children, numbered $1, 2, \\ldots, N$. They 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$ candie","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_m"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$a_1$ $a_2$ $\\ldots$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_m","tags":[],"sample_group":[["3 4\n1 2 3","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."],["1 10\n9","0\n\nThere may be no ways for the children to share candies."],["2 0\n0 0","1\n\nThere is one way for the children to share candies, as follows:\n\n*   $(0, 0)$"],["4 100000\n100000 100000 100000 100000","665683269\n\nBe sure to print the answer modulo $10^9 + 7$."]],"created_at":"2026-03-03 11:01:14"}}