# Untitled

unknown
plain_text
a month ago
1.8 kB
12
Indexable
Never
```public class Solution {
HashMap<Long, Long> hm = new HashMap<>();
int mod = (int)(1e9+7);

public long fastPow(int a, long n){
if(n == 0){
return 1;
}

long res = fastPow(a, n/2) % mod;

if(n % 2 == 0){
return (res*res) % mod;
}
else{
return (((res * res) % mod) * a) % mod;
}
}

private long nCr(long n, long r) {
if (r > n) {
return 0;
}
if (r == 0 || n == r) {
return 1;
}

if (hm.containsKey(n * mod + r)) {
return hm.get(n * mod + r);
}

long result = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % mod;
hm.put(n * mod + r, result);
return result;
}

public long findWays(long n){
if(n == 0){
return 0;
}
if(n == 1 || n == 2){
return 1;
}

if(hm.containsKey(n)){
return hm.get(n);
}

//h is the second last level of the tree as the elements are completely filled till 2nd last level
//the above is the property of complete binary tree
long h = (long)(Math.log(n) / Math.log(2));
long x = ((long)fastPow(2, h) - 1) % mod;

long leftCount = ((long)x-1)/2;
leftCount = (leftCount + Math.min(n - x, ((long)x+1)/2)) % mod;

long rightCount = ((long)n - 1 - leftCount) % mod;

long ways = (nCr(n-1, leftCount)) % mod;
hm.put(n, (long)((((ways * findWays(leftCount)) % mod) * findWays(rightCount)) % mod));

return hm.get(n);
}

public int solve(int A) {
return (int)(findWays(A) % mod);
}
}
```