VNOI Marathon 08

Đếm số đường đi trên đồ thị đầy đủ

Một đồ thị đầy đủ N đỉnh là đồ thị mà giữa mọi cặp đỉnh đều có cạnh nối. Bạn hãy đếm số đường đi giữa 2 đỉnh bất kì của đồ thị. Lưu ý rằng một đường đi không được đi qua một đỉnh quá một lần.

Dữ liệu

Ghi duy nhất một số N là số đỉnh của đồ thị (2 ≤ N ≤ 1000).

Kết quả

In ra một số duy nhất là số lượng đường đi giữa 2 đỉnh bất kì.

Ví dụ

Dữ liệu
4

Kết quả
5

Giải thích
Giữa 2 đỉnh bất kì ví dụ đỉnh 1 và 2 có 5 đường đi:
1-2
1-3-2
1-3-4-2
1-4-2
1-4-3-2