A TV remote

There is a TV remote that contains three buttons:

1. Next channel
2. Previous channel
3. Volume change

Find the number of ways such that after \(N\) clicks on the remote you remain on the same channel.

You can assume there are infinite channels.

Since the answer can be too large, print answer modulo \(1000000007\).

Example:

Input:  2
Output: 3

Approach

Java

public class ATVRemote {
    static int[] fact = new int[100001];
    static int[] inv = new int[100001];
    static final int mod = 100_000_000_7;

    public static void main(String args[]) {
        factFinder();
        invFinder();

        int n = 2;
        long sum = getATVRemote(n);

        System.out.println(sum);
    }

    static int powerMod(long x, long y) {
        // Initialize result
        long res = 1;

        // Update x if it is more
        // than or equal to p
        x = x % mod;

        if (x == 0)
            return 0; // In case x is divisible by p;

        while (y > 0) {
            // If y is odd, multiply x
            // with result
            if ((y & 1) == 1)
                res = (res * x) % mod;

            // y must be even now
            // y = y / 2
            y = y >> 1;
            x = (x * x) % mod;
        }
        return (int) res;
    }

    // pre computation
    public static void invFinder() {
        for (int i = 0; i < 100001; i++)
            inv[i] = powerMod(fact[i], mod - 2);
    }

    // pre computation
    public static void factFinder() {
        fact[0] = 1;
        for (int i = 1; i < 100001; i++)
            fact[i] = (int) (((long) fact[i - 1] * i) % mod);
    }

    public static long getATVRemote(int n) {
        long sum = 0;
        for (int i = 0; i <= n; i++) {
            int e = n - i;
            int box = n - i + 1;
            int balls = i;

            int m = box + balls - 1;
            int r = box - 1;

            if (e % 2 == 0) {
                long z = 1;
                if (r >= 0)
                    z = ((((long) fact[m] * inv[m - r]) % mod) * inv[r]) % mod;
                long boxper = ((fact[e] * (long) inv[e / 2]) % mod) * inv[e / 2] % mod;
                sum = (sum + ((boxper * z)) % mod) % mod;
            }
        }
        return sum;
    }

}