Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Biswa the Digital Gutibaj

Limits: 1s, 256 MB

Being a digital gutibaj, Biswa is virtually busy with all his evil stuff all the time. As he is a digital guy, all the evidence of his stuff are present on his computer. He’s suspecting that his good friend Jesi has somehow gained access to his computer (Biswa is a weirdly obsessed guy and he suspects weird things all the time. No big deal!). Now he’s afraid that all the evidence of his gutibaji may come to light and wants to change the password of his computer.

He’ll follow a procedure to generate the new password. Initially he’s got some files. All files contain some characters written on it. All the characters in a single file are same and no two different files has the same character. From these files he’ll generate a password of length L exactly. To generate the password he’ll choose a file, copy some characters from it, add those characters to the end of the password (initially the password is empty) and finally delete that file. He may use one or more files to generate this password. No file can be used more than once and it is possible that some files may not be used at all. Now he wonders how many different passwords of length L can be generated following this procedure.

Are you up for helping Biswa just to score a problem?


First line of the test case will contain the number of files N (1 ≤ N ≤ 10) and the required length of the password L (1 ≤ L ≤ 1012).

The following line will contain N numbers (A1, A2, …, AN) where the i-th number Ai (1 ≤ Ai ≤ 1012) is equal to the number of characters in the ith file.


You have to print the number of passwords that can be generated following the described procedure. As this number can be pretty large you have to print the remainder of this number after dividing it by 1000000007.


2 5
4 3
3 10
3 5 3