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 (no of test cases)

Next T line will contain N no of vertices

Output

No of intersections of diagonals as specified.

Example

Input:
2
4
5
Output:

1
5

 < 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:-) kanishtalwar: 2015-10-27 19:24:04 Last edit: 2015-10-27 19:26:03 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?