SPOJ.com - Problem DIG

DIG - DIAGONAL

no tags

You are a given a n sided convex polygon. Find total number of intersections of all diagonals.

Assume that all the intersection points are different.

If in case answer exceeds 10^9 + 7 , take modulo 10^9 + 7

1<=n<=10^8

Input

First Line : T (number of test cases)

Next T line will contain N number of vertices

Output

Number of intersections of diagonals as specified.

Example

Input:
2
4
5

Output:
1
5

Submit solution!

hide comments

< Previous 1 2 Next >

	aaditya111: 2017-07-19 14:05:03 Use 24*10000000007L for taking modulo in c ,lest u will get stroked!
	vineetpratik: 2016-07-06 14:02:05 derive formula and then modular division/multiplication AC
	mkfeuhrer: 2016-07-05 15:23:08 easy if u knw the formula!! formula derivation requires some work!! i did dat while my jee prep.(chp = P& C) :-P glad i remember it till now :-) AC 1 go:-)
	Francky: 2014-05-29 22:50:01 @candide : Suppose for a while «diagonal means unbounded», what would be the interest to specify "convex" ? ans=NULL. Now suppose the opposite, "convex" makes sens in the problem statement. In this condition, we can honestly assert «here, diagonal means bounded». It's always good to be as precise as possible. Many thanks to candide for his rigorous catch. Here the description seems robust enough.
	candide: 2014-05-29 22:12:51 @flago Convexity is not sufficient. Specifically, depends on what you mean by "Diagonal": is it a "line" (non bounded region) or a "segment line" (bounded region).
	Flago: 2014-05-28 15:35:05 @candide : given a convex polygon, so it is specified.
	candide: 2014-04-26 08:42:47 Interesting question, not tutorial at all. But problem statement is ambiguous : the fact that diagonal intersections to be INSIDE the polygon is not specified. There is a similar formula for the case where you don't care about the position of the intersection. Moreover, examples are poorly chosen for not allowing to discriminate the two cases. Another remark : cases n=1 and n=2 are meaningless. Last edit: 2014-04-26 08:44:21
	Francky: 2012-08-09 17:35:41 Arghh, convex is very important, I first solved for diagonal lines of any polygon.
	:D: 2012-08-08 13:56:53 I didn't find it trivial just easy. Is it easy because there's a know formula for it or is it really so basic to construct the formula on your own?
	devu: 2012-08-02 10:03:27 It is not a tutorial problem,nice concept behind it,nice problem

Submit solution!

Added by:	praveen123
Date:	2012-08-01
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	general problem