선물 교환

행사에 참가한 모든 사람은 선물을 하나씩 준비했다.

행사가 끝난 뒤, 준비한 선물을 서로 나누어 주려고 한다. 모든 사람은 선물을 정확히 하나씩 받아야 하며, 자기 자신이 준비한 선물을 받는 사람은 없어야 한다.

이 조건을 만족하도록 선물을 전달하는 경우의 수를 구하시오.

첫째 줄에 참가자 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

조건을 만족하는 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.