CWAY - Counting paths in a complete graph

no tags 

A complete graph of N verticles is a graph in which there is an edge between every pair of nodes.

Your task is to count the number of paths between any pair of nodes in the graph. Note that a path cannot visit a vertex more than once.

Input

A single integer N that is the number of verticles in the graph (2 ≤ N ≤ 1000).

Output

A single integer that is the number of paths between any two nodes in the graph.

Example

Input
4

Output
5

Description
For example, there are 5 paths between 1 and 2:
1-2
1-3-2
1-3-4-2
1-4-2
1-4-3-2

hide comments
lnxdx: 2017-06-15 23:44:48

100 but we should use big integers. The answer for n = 1000 is extremely large.
I couldn't use C++. Instead I use python.

:.Mohib.:: 2015-10-02 12:04:41

Nice one...!! :)

:D: 2009-08-04 19:49:47

I got 100 instead of 90 when I took into account N<2 (result 0 since there aren't any two distinct nodes).

Last edit: 2009-08-04 19:50:09

Added by:Lê Đôn Khuê
Date:2008-06-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon '08 - Round 3/DivB
Problem Setter: Lê Đôn Khuê