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+7N  10^9 Example 1 Input3 Output2 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 2Input4 Output6 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 1000000007unsigned 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?
Find all combinations of a number sequence which is first increasing then decreasing
performance;algorithm;c;combinatorics
BugInput : 500000003Output: 18446744073709551615The 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)\$.