Selection of Cities

James has decided to take a break from his work. He makes a plan to visit India for a few days with his family. He knows a lot about India, and also about the various cities he could visit. He decides to write down all the cities on paper. Let the number of cities be n. Now, he shows the list to his wife and asks her, the city/cities she wants to visit. He tells her that she can select any city/cities and any number of cities. The wife says she needs a day to decide.

After this, James calls his son and tells him all about the trip, and the list of cities. He gives him a task and asks him, the number of ways the city/cities can be chosen from the list if the total number of cities written on the list is n. The cities are numbered from 1 to n. At least 1 city has to be selected.

He now asks your help to find the answer to the question that was asked to him.

Example:

Input:  n = 2
Output: 3

Approach

Java

public class SelectionOfCities {
    public static void main(String[] args) {

        long n = 2;

        System.out.println(power(2, n) - 1);

    }

    static long mod = 1000000007;

    static long power(long a, long b) {
        if (b == 0)
            return 1;
        long res = power(a, b / 2) % mod;

        if (b % 2 == 0)
            return (res % mod * res % mod) % mod;

        return ((res % mod * res % mod) % mod * a % mod) % mod;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

long long int power(long long int a, long long int b)
{
    if (b == 0)
        return 1;
    long long int res = power(a, b / 2) % mod;

    if (b % 2 == 0)
        return (res % mod * res % mod) % mod;

    return ((res % mod * res % mod) % mod * a % mod) % mod;
}
int main()
{

    long long int n = 2;

    cout << power(2, n) - 1 << "\n";

    return 0;
}