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^9Example 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?