B'Devu wants to decorate his garden with flowers. He has purchased n boxes, where the i-th box contains fi flowers. All flowers in a single box are of the same color (hence they are indistinguishable). Also, no two boxes have flowers of the same color. Now Devu wants to select exactly s flowers from the boxes to decorate his garden. Devu would like to know, in how many different ways can he select the flowers from each box? Since this number may be very large, he asks you to find the number modulo (109 xe2 x80 x89+ xe2 x80 x897). Devu considers two ways different if there is at least one box from which different number of flowers are selected in these two ways. The first line of input contains two space-separated integers n and s (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x8920, 0 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89s xe2 x80 x89 xe2 x89 xa4 xe2 x80 x891014). The second line contains n space-separated integers f1, xe2 x80 x89f2, xe2 x80 x89... fn (0 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89fi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x891012). Output a single integer -- the number of ways in which Devu can select the flowers modulo (109 xe2 x80 x89+ xe2 x80 x897). Sample 1. There are two ways of selecting 3 flowers: {1, xe2 x80 x892} and {0, xe2 x80 x893}. Sample 2. There is only one way of selecting 4 flowers: {2, xe2 x80 x892}. Sample 3. There are three ways of selecting 5 flowers: {1, xe2 x80 x892, xe2 x80 x892}, {0, xe2 x80 x893, xe2 x80 x892}, and {1, xe2 x80 x893, xe2 x80 x891}.'...