SPOJ.com - Problem MMFTEAM

MMFTEAM - Team formation

#combinatorics

Coach has n players. A team is a subset of players and has at least two players - a captain and a keeper. How many ways can a coach form a team from n players?

Input

Each line of input contains one random integer number 2 ≤ n ≤ 10⁶ (1 000 000). Input terminates with 0 (zero).

Output

For each n print your answer modulo 1 000 000 007 on new line.

Example

Input:
2
3
0

Output:
2
12

22/06/2019 - Time limit increased.

Submit solution!

hide comments



	kuzinat0r: 2022-09-19 21:56:18 Could you please provide me with the test input which I get wrong? I ran out of ideas. My algorithm provides exactly the same result as a direct calculation - and yet I still get wrong answer...
	jpietras: 2019-06-18 18:34:53 This is for sure not possible in c#... I tested writing result of 1 + 1 for each test case and it already exceeds the time. Please fix this. <== Reply. There is ACC solution in JAVA - 1.57s. My Python2 solution - 4.7s. Try to optimise your algo and I/O. Regards. Last edit: 2019-06-21 13:30:06
	jpietras: 2019-06-18 18:30:05 Is this even solveable in c#? I timed out so many times I can barely count anymore. The data set is so huge for c# that reading it and outputting 0 without any calculations for each test case already takes 2.3sec out of 3 seconds.
	JY: 2019-05-23 12:58:52 The problem statement is not clear. A team can have only one captain and one keeper. <== Reply. Yes! Only one captain and one keeper (different players). Last edit: 2019-05-25 11:41:58
	hungneymar: 2019-04-27 16:36:34 độ phức tạp o(nsố test) cũng ko qua nổi test 2??? <== Reply. Please write your questions and comments in English. Thanks. Last edit: 2019-04-29 12:52:18*

Submit solution!

Added by:	julkas
Date:	2018-07-03
Time limit:	4s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All