Азиатско-Тихоокеанская олимпиада по математике 2006 года | Казахстанские олимпиады

Пусть $p\geq 5$ является простым числом и пусть $r$ есть число всевозможных различных способов размещения p шашек на шахматной доске размера $p\times p$ таким образом, что не все шашки лежат на одной строке (но все они могут находиться в одном столбце). Докажите, что $r$ делится на $p^5$. Здесь мы полагаем, что все шашки идентичны.