There are \(n\) stone piles. Initially, the \(i\)-th pile contains \(a_i\) stones.

Consider a set of ranges \([L_i, R_i]\). For each range, you put one stone into every pile in that range.

A range set is called nice if it satisfies two conditions:

• after you put all stones according to the ranges, each pile will contain \(K\) stones,
• there are no nested ranges (i.e. no \(i\), \(j\) such that \(L_i \le L_j \le R_j \le R_i\)).

How many different nice sets are there? Two sets are considered different if one of them contains a range that is not present in another one.

Input

The first line contains two integers \(N\) and \(K\) denoting the number of piles and the desired number of stones in each pile. The second line contains \(N\) integers \(a_i\) which are the initial pile sizes.

• \(1 \le N \le 10^5\)
• \(1 \le K \le 10^9\)
• \(1 \le a_i \le 10^9\)

Output

Print the number of nice sets modulo \(10^9+7\).

Example

Input 1:

6 3
2 1 2 3 2 2

Output 1:

2

Explanation

Input 1: Nice sets in the sample are \(([1, 2], [2, 3], [5, 6])\) and \(([1, 2], [2, 3], [5, 5], [6, 6])\).