# Rooks

Author: aruzhan
Problem has been solved: 16 times

Русский язык | English Language

Given a chessboard of size $2020 \times 2020$, consider $r$ - an arrangement of $2020$ rooks on this board in such a way that no two rooks attack each other. We call $d(r)$ the number of rooks in the arrangement $r$ that stand on the main diagonal connecting the lower left and the upper right corners. Let $X$ be the set of all possible arrangements of $r$ in which no two rooks attack each other. Consider the sum $S = \sum_{r \in X} d(r)^4$. Find the maximum natural number $k$ such that $S$ is divisible by $3^k$.