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&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
#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 &gt; 0){
        if(n &amp; 1){
            res = res * x;
            res = res%m;
        }
        x = x * x;
        x= x%m;
        n &gt;&gt;= 1;
    }
    return res;

}


int main(){

    unsigned long long int n,res=0,temp=1,i;
    scanf("%llu", &amp;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?
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)\$.