# PROBLEM LINK : https://www.codechef.com/NPLQ2019/problems/NPLQ19E

*Author:* Shivang Awasthi

*Tester:* Shivang Awasthi

*Editorialist:* Shivang Awasthi

# DIFFICULTY:

Simple

# PREREQUISITES:

Math, Combinatorics

# PROBLEM:

Find the number of ways to divide a set of size N into even and odd sized non empty subsets.

# QUICK EXPLANATION:

The answer is there are pow(2,N-1)-1 and pow(2,N-1) even and odd sized non empty subsets

# EXPLANATION:

Considering (N,r) for r < 0 and r > N is 0,

the number of even sized subsets is sum of (N,2*r) for r running from 0 to N/2, and the
number of odd sized subsets is sum of (N,2*r+1) for r running from 0 to N/2.

The sum of (N,2

*r) for r running from 0 to N/2 is pow(2,N-1).*

The sum of (N,2r+1) for r running from 0 to N/2 is also pow(2,N-1).

The sum of (N,2

These are the popular results from combinatorics and can be verified from here and here.

As we don’t need empty subset,

the answer for even sized subsets is pow(2,N-1)-1.

the answer for odd sized subsets is pow(2,N-1)-1.

The answer for N = 0 is 0 for both even and odd sized subsets .

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll N = 3000;
const ll MOD = (ll)1e9+7;
const ll inf = (ll)1e18+6;
// const ll M = (ll)2000;
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
ll add(ll x, ll y) {
x += y;
if (x >= MOD) return x - MOD;
return x;
}
ll sub(ll x, ll y) {
x -= y;
if (x < 0) return x + MOD;
return x;
}
ll mult(ll x, ll y) {
return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
if (p == 0) return 1;
if (p & 1) return mult(x, bin_pow(x, p - 1));
return bin_pow(mult(x, x), p / 2);
}
ll rev(ll x) {
return bin_pow(x, MOD - 2);
}
bool cmp(pll A, pll B)
{
return A.fi * B.se + A.se < B.fi * A.se + B.se;
}
int main()
{
ios::sync_with_stdio(true);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("input.txt", "rt", stdin);
#endif
ll t;
cin >> t;
while(t--)
{
ll n;
cin >> n;
if(n == 0)
cout << 0 << " " << 0 << "\n";
else
cout << (bin_pow(2, n - 1) - 1 + MOD) % MOD << " " << bin_pow(2, n - 1) << "\n";
}
}
```