time limit per test: 0.25 sec.
memory limit per test: 65536 KB

input: standard
output: standard

Let's define a board as a finite subset of infinite chessboard cells. The (b_1, b_2, ..., b_n) board is the board with n left-aligned rows. The i-th line consists of b_i sequential cells. For example, (1, 4, 3, 5) board looks as follows:



The rook can be placed on any cell of the board. The rooks disposition is called peaceful if and only if no two rooks stay on the same vertical or horizontal line (no matter if all cells between them belong to the (b_1, b_2, ..., b_n) board or not).
Your task is to find a number of peaceful dispositions of k rooks for the (b_1, b_2, ..., b_n) board.

The first line of the input file contains two integer numbers n and k (1 <= n, k <= 250). The second line contains n space-delimited numbers (b_1, b_2, ..., b_n) (1 <= b_i <= 250, i=1..n).

Write to the output single integer -- number of different peaceful rooks dispositions on the given board.

Input

Test #1
2 2
2 3

Test #2
3 3
2 1 2