ITPTIT ICPC 2021

Time Limit: 1s

Lema hôm nay đang rất vui vẻ nên đã giao cho Bi một bài toán khá “dễ”, với 1 phần thưởng là một cuộc hẹn đi chơi ở Hồ Gươm.

Bi được Lema cho 1 vòng tròn và n điểm nằm trên vòng tròn đó. Biết n là 1 số chẵn và các điểm đều đối xứng với nhau qua tâm vòng tròn. Bài toán đặt ra là tìm số cách ghép cặp các điểm với nhau sao cho tạo thành những đường thẳng không giao cắt với nhau.

Để dễ hình dung, Lema đã chỉ cho Bi 2 ví dụ:

• Với n = 4, kết quả sẽ ra 2 cách như sau:

• Với n = 6, kết quả sẽ ra 5 cách như sau:

Các bạn hãy giúp Bi có được cuộc hẹn này nhé. Vì kết quả có thể rất lớn nên sẽ lấy phần dư của kết quả chia cho 10⁹+7.

Input:

1 số duy nhất ghi n là số lượng điểm nằm trên vòng tròn (2 ≤ n ≤ 1000; n%2 = 0)

Output:

Số cách chọn sau khi chia dư cho 10⁹+7.

Example: