#### Registered Users Only

Please login to view and utilize this feature.

## Problem Description

Coco the Monkey is performing at a circus and is currently handing out colourful balloons to the audience.

Coco the Monkey has balloons of *N* colours numbered from 1 to *N*. Coco the Monkey has *A _{i}* balloons of the

*i*th colour. Each person in the audience gets exactly

*K*balloons.

Damian and Fan Pu have come to see Coco the Monkey perform at the circus. As they watch Coco the Monkey distribute balloons, Damian wonders, how many different possible combinations of colours of balloons Coco the Monkey can give someone in the audience? Two combinations are considered distinct if the number of balloons present in one combination and in another combination is different for a certain colour.

Damian asks Fan Pu his question, but Fan Pu wants to watch the performance. As such, can you help Damian calculate the answer, modulo 10^{9} + 7?

## Input

The first line of input will contain two integers, *N* and *K*.

The following line of input will contain *N* space separated integers, *A _{i}*.

## Output

Output a single integer, the number of distinct combinations, modulo 10^{9} + 7.

## Limits

Subtask 1 (14%): 1 ≤ *N* ≤ 3. 1 ≤ *K* ≤ 1500. 1 ≤ *A _{i}* ≤ 1000.

Subtask 2 (29%): 1 ≤ *N* ≤ 20. 1 ≤ *K* ≤ 10^{4}. 1 ≤ *A _{i}* ≤ 1000.

Subtask 3 (57%): 1 ≤ *N* ≤ 20. 1 ≤ *K* ≤ 10^{14}. 1 ≤ *A _{i}* ≤ 10

^{12}.

Subtask 4 (0%): Sample Testcases

## Sample Testcase 1

### Input

3 5 1 3 2

### Output

3

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 14 | 30 | 1s | 64MB | Minimum |

2 | 29 | 60 | 1s | 64MB | Minimum |

3 | 57 | 110 | 1s | 64MB | Minimum |

4 | 0 | 1 | 1s | 64MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o balloons -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512