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

Question

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?

Answer 1

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)\$.