{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003eLet\u0027s 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: \u003cbr\u003e \u003cbr\u003e\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\"\u003e\u003ctbody\u003e\u003ctr height\u003d\"40\"\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\"\u003e\u003ctbody\u003e\u003ctr height\u003d\"40\"\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\"\u003e\u003ctbody\u003e\u003ctr height\u003d\"40\"\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\"\u003e\u003ctbody\u003e\u003ctr height\u003d\"40\"\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003ctd width\u003d\"40\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e \u003cbr\u003e \u003cbr\u003eThe 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). \u003cbr\u003eYour task is to find a number of peaceful dispositions of k rooks for the (b_1, b_2, ..., b_n) board. \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eThe first line of the input file contains two integer numbers n and k (1 \u0026lt;\u003d n, k \u0026lt;\u003d 250). The second line contains n space-delimited numbers (b_1, b_2, ..., b_n) (1 \u0026lt;\u003d b_i \u0026lt;\u003d 250, i\u003d1..n). \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eWrite to the output single integer -- number of different peaceful rooks dispositions on the given board. \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTest #1 \u003cbr\u003e2 2 \u003cbr\u003e2 3 \u003cbr\u003e \u003cbr\u003eTest #2 \u003cbr\u003e3 3 \u003cbr\u003e2 1 2 \u003cbr\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTest #1 \u003cbr\u003e4 \u003cbr\u003e \u003cbr\u003eTest #2 \u003cbr\u003e0 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003eMichael R. Mirzayanov \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003eACM ICPC 2004-2005, NEERC, Southern Subregional Contest \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003eSaratov, October 7, 2004 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}