Harry Potter and the Vault of Gringotts

Sherlock221b Tough Cubs' Contest, Dece...
Limits 1s, 512 MB

"There was a break-in of Gringotts Wizarding Bank on 1 May, 1998, during the height of the Second Wizarding War. It was carried out by Harry Potter, Ron Weasley, and Hermione Granger in order to steal one of Lord Voldemort’s Horcruxes from the vault belonging to the Lestrange family. The trio broke into the bank with Hermione disguised as Bellatrix Lestrange, Ron given a fake identity as a disguise, while Harry under the Invisibility Cloak. They found their way into the vault and acquired Helga Hufflepuff's Cup, and in their attempt to escape ended up flying a half-blind dragon out of the bank in what would become a famous escape. This break-in is, to date, the only known successful robbery of Gringotts."

After passing through all the other obstacles, Harry finds himself in front the vault of Helga Hufflepuff's Cup, with only one obstacle in front of him. He needs to enter the correct passcode to get inside the vault. There is a keypad in front of the vault consisting of the digits from 0 to 9 where he needs to enter the passcode. "What sorcery is this" - Harry muttered to himself, being unfamiliar with muggle technology. Harry's close associate Miss Hermione Granger, who grew up in the muggle world, came to his rescue and did a fingerprint analysis of the keypad. The keys she found goblin fingerprints on are the keys that have been used to enter the passcode (so each of them have been used at least once). Now, before Harry magically conjures up the secret passcode, he needs to know how many possible passcode there are that fits the description. Harry knows for sure that the passcode won't exceed a certain length.

Input

In the first line of the input, there are two numbers N (1 ≤ N ≤ 10) denoting the number of keys that have been pressed and K (1 ≤ N ≤ K ≤ 100) denoting the maximum length of the passcode. In the next line, there are N space separated distinct digits from 0 to 9, denoting the keys that have been pressed.

Output

In a single line, print the number of possible passcodes. Since the answer can be huge, print the answer modulo 109+7. Please note that unlike traditional numbers, the passcode can contain leading zeros.

Samples

InputOutput
3 3
4 7 2
6
InputOutput
2 3
0 1
8

Explanation

In the second test case, there are 2 passcodes (01, 10) of length 2. There are 6 passcodes (001, 010, 011, 100, 101, 110) of length 3. In total, there are 8 passcodes.

Submit

Login to submit.

Statistics

40% Solution Ratio
ruhanhabib39Earliest, Dec '16
ArobindoFastest, 0.2s
Tarik.amtolyLightest, 131 kB
ruhanhabib39Shortest, 594B
Toph uses cookies. By continuing you agree to our Cookie Policy.