반별 급식 순서를 짜는 영일이는 지난번에 학급별 친밀도를 고려한 급식 순서를 만들어 매우 큰 호응을 받았다.
이번에 영일이는 지난 번 반별 급식 순서와는 다른 새로운 급식 순서를 만들기로 하였다.

이번에는 지난번 순서와는 다른 순서로 변경해야하는데, 어떤 반도 지난번과 같은 순번으로 배치되면 안 된다.
예를 들어, 지난번에 두 번째 순번이었는데 이번에도 똑같이 두 번째 순번으로 배치되면 안 되는 것이다.

지난번 반별 급식 순서가 1 2 3 이었다면, 2 3 1 또는 3 1 2 로 변경하는 것은 가능하다.
하지만, 1 3 2 로 변경하는 것은 불가능하다. 1반의 순번이 같기 때문이다.



 이전 반별 급식 순서가 주어질 때, 만들어 낼 수 있는 새로운 급식 순서의 개수를 계산해보자.

첫째 줄에는 학급 수가 주어진다.
둘째 줄에는 반별 급식 순서가 스페이스를 사이에 두고 한 줄로 입력된다.
(1<=반 개수<=2000, 반 번호는 중복 입력되지 않는다.)

만들어 낼 수 있는 새로운 급식 순서의 개수를 1,000,000,009로 나눈 나머지를 출력한다.

 2021GTPC