A team of coders has participated in n contests. The score for each contest is an integer between 0 and 10, and the total score is the sum of the scores.

You know the total score of the team and some scores for individual contests. Your task is to calculate the number of ways the team may have achieved the total score.

Input

The first input line contains two integers n and s: the number of the contests and the total score.

The second input line contains n numbers, and describes the scores of the contests. Each number is either ? or an integer between 0 and 10. Value ? means that the score is unknown, and otherwise the number is the score.

Output

Output one integer: the number of ways to achieve the total score. The answer may be large so output it modulo 10^9+7.

You may assume that there is at least one solution.

Constraints

• 1 \le n \le 100
• 0 \le s \le 1000

Example

Input:

4 25
8 ? 3 ?

Output:

7