Non-Attacking Vassals Arrangement

A long time ago, there was a mighty empire with a square-shaped territory. The empire was divided into a grid of n × n cells. The king planned to grant one cell to each of his loyal vassals as their fief. However, these vassals were belligerent. If any two vassals were placed in the same row or the same column, they would start a conflict.

To ensure peace, the king wishes to arrange the positions of exactly k vassals on the grid so that no two of them lie in the same row or same column. In other words, for any two chosen cells, if the cells are at positions \( (i_1, j_1) \) and \( (i_2, j_2) \), then it must hold that \( i_1 \neq i_2 \) and \( j_1 \neq j_2 \). The number of valid arrangements is to be computed modulo 504.

Hint: The number of ways to choose k rows and k columns is \(\binom{n}{k}\) each, and once they are chosen, the number of ways to assign the cells is \(k!\). Thus, the total number of valid arrangements is \(\binom{n}{k}^2 \times k!\) (if \(k \leq n\)); otherwise, if \(k > n\) then no valid arrangement exists.

The input guarantees \(n \leq 100\) and \(k \leq 2n^2-2n+1\). Note that when \(k>n\) the answer is 0.

inputFormat

The first and only line of input contains two integers n and k, where n (\(1 \le n \le 100\)) is the side length of the square territory and k is the number of vassals to be placed.

outputFormat

Output a single integer representing the number of possible arrangements modulo 504.

sample

3 2

18