269. Rooks

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.

Sample test(s)

Test #1
2 2
2 3

Test #2
3 3
2 1 2

Test #1

Test #2

Author:Michael R. Mirzayanov
Resource:ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:Saratov, October 7, 2004

Server time: 2016-08-29 00:32:06Online Contester Team © 2002 - 2016. All rights reserved.