|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Дмитрий Шевченко, ВлГУ.
Chess is a well known game, which also serves as a rich source of different
math problems. Let us recall briefly characteristics of two chess pieces:
- The rook can move from it's current position only in horizontal or
vertical directions on any distance. Two rooks attack each other, if one
is on the path of the other.
- The knight moves the following way: first he moves 2 squares in
horizontal or vertical direction and then 1 square in the perpendicular
direction. In contrast to rooks, figures on the way of knight do
not interfere with its movement. Two knights attack each other if
they can move to each other's cells.
For centuries mathematicians have been solving problems like "Find the
total number of ways one can put k rooks (or knights) on a chessboard so
that no two of them are in the attacking positions". You will have to solve
this problem too, but for a chess piece designed specially for you - the
knightrook. This piece moves like the knight in northeastern
direction and like the rook in southwestern direction. This chess
piece is shown in figure 1. The initial location of knightrook is marked
with a star. The cells that the knightrook can move to from initial location
are marked with gray color. Two knightrooks attack each other if one
is on the path of the other. Note that relation "attack" is not mutual
here, in contrast to rooks and knights. If the knightrook attacks another
one, the contrary is not true, but we still consider this an attacking
position.
You must find the total number of ways one can put k knightrooks on
an n x m chessboard so that no two of them are in the
attacking positions. n is the number of chessboard rows (northern
direction) and m is the number of chessboard columns (eastern
direction).
Input
The first line contains three integers n, m and k
separated by spaces (1 ≤ n ≤ 8, 1 ≤ m ≤ 17,
0 ≤ k ≤ n * m).
Output
Print a line containing the total number of ways one can put the given
number of knightrooks on an n x m chessboard so that no two of them are
in attacking positions.
|
Input 1
|
Output 1
|
2 2 1
|
4
|
|
Input 2
|
Output 2
|
2 2 3
|
0
|
Для отправки решений необходимо выполнить вход.
|