import java.math.BigInteger;
import java.util.*;

public class Euler494 {
    static BigInteger fib(int n) {
        if (n <= 0)
            return BigInteger.ZERO;
        if (n <= 2)
            return BigInteger.ONE;
        BigInteger a = BigInteger.ONE, b = BigInteger.ONE;
        for (int i = 2; i < n; i++) {
            BigInteger c = a.add(b);
            a = b;
            b = c;
        }
        return b;
    }

    static int collLength(BigInteger n) {
        int len = 0;
        while (!n.and(n.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)) {
            len++;
            if (n.testBit(0))
                n = n.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE);
            else
                n = n.shiftRight(1);
        }
        return len;
    }

    static BigInteger countBack(List<BigInteger> sources, List<Integer> steps) {
        BigInteger ans = BigInteger.ZERO;
        for (int i = 0; i < sources.size(); i++) {
            BigInteger n = sources.get(i);
            int s = steps.get(i);
            if (s < 0)
                continue;
            if (n.mod(BigInteger.valueOf(3)).equals(BigInteger.ZERO))
                s = 0;
            // Expand backward s steps
            List<BigInteger> states = new ArrayList<>();
            states.add(n);
            for (int step = 0; step < s; step++) {
                List<BigInteger> next = new ArrayList<>();
                for (BigInteger a : states) {
                    next.add(a.shiftLeft(1));
                    if (a.mod(BigInteger.valueOf(6)).intValue() == 4)
                        next.add(a.divide(BigInteger.valueOf(3)));
                }
                states = next;
            }
            ans = ans.add(BigInteger.valueOf(states.size()));
        }
        return ans;
    }

    static BigInteger solveF(int steps) {
        int[] seeds = { 9, 19, 37, 51, 155, 159 };
        List<BigInteger> sources = new ArrayList<>();
        List<Integer> stepsList = new ArrayList<>();
        for (int s : seeds) {
            sources.add(BigInteger.valueOf(s));
            stepsList.add(steps - collLength(BigInteger.valueOf(s)));
        }
        return fib(steps).add(countBack(sources, stepsList));
    }

    public static void main(String[] args) {
        System.out.println(solveF(90));
    }
}