# Find all combinations of a number sequence which is first increasing then decreasing

Given an integer N(Natural Number), A program/Algorithm to find the remainder of arrangements that can be obtained by rearranging the numbers 1, 2, ...., N.

Input Format: One line containing the integer N

Output Format: An integer m, giving the remainder of the number of arrangements that could be obtained from 1, 2, ...., N is divide by Mod

Constraints:
Mod = 10^9+7
N ≤ 10^9

Example 1

Input
3
Output
2
Explanation:
Consider the first three natural numbers 1, 2, 3. These can be arranged in the following ways: 2, 3, 1 and 1, 3, 2. In both of these arrangements, the numbers increase to a certain point and then decrease. There are two such arrangements: 2, 3, 1 and 1, 3, 2.

Example 2

Input
4
Output
6
Explanation:
The six arrangements are (1, 2, 4, 3), (1,3,4,2), (1,4,3,2), (2,3,4,1), (2,4,3,1), (3,4,2,1).

#include<stdio.h>
#include<stdlib.h>
#define m 1000000007

unsigned long long int power(unsigned long long int x, unsigned long long int n){

unsigned long long int res = 1;
while(n > 0){
if(n & 1){
res = res * x;
res = res%m;
}
x = x * x;
x= x%m;
n >>= 1;
}
return res;

}

int main(){

unsigned long long int n,res=0,temp=1,i;
scanf("%llu", &n);
if(n==1 || n==0){
printf("0\n");
return 0;
}
temp = power(2, n-1);
temp--;
temp--;
printf("%llu\n", temp);

return 0;
}


Can Anyone Solve This with Better Time Complexity?

• An explanation of the combinatorics behind the scenes would be most helpful. – vnp Aug 4 '17 at 6:27

### Bug

Input : 500000003
Output: 18446744073709551615


The problem is that the result of your power() call could be 0 or 1. Then when you subtract 2, you get a negative number. Given the input constaint of $n ≤ 10^9$, 500000003 is the only bad input, but in general this happens when n is any multiple of 500000003. To correct this, you could change this:

temp--;
temp--;


to:

temp = (temp + m - 2) % m;


This ensures that temp will remain positive. Time complexity wise, your program is great at $O(\log n)$.

• It has to deal with only natural number then why to count 0 ? – Himanshu Ray Aug 4 '17 at 6:47
• Why the answer is $2^{n-1} - 2$ is quite clear. I wanted OP to confirm that he knows that. You shouldn't interfere. I know that you know. Sorry. – vnp Aug 4 '17 at 6:51
• @HimanshuRay Apparently you didn't really understand the problem so I removed my explanation. – JS1 Aug 4 '17 at 8:25
• @vnp I think you were right, judging from the above comment by OP. – JS1 Aug 4 '17 at 8:26
• my mistake @JS1 sorry. You can put back your Explanation. I will go through it once more. – Himanshu Ray Aug 4 '17 at 9:10