public class Euler178 {
    public static void main(String[] args) {
        int maxD = 40, ALL = (1 << 10) - 1;
        long[][][] dp = new long[maxD + 1][1 << 10][10];
        for (int d = 1; d <= 9; d++)
            dp[1][1 << d][d] = 1;
        for (int ln = 1; ln < maxD; ln++)
            for (int mask = 0; mask < (1 << 10); mask++)
                for (int d = 0; d <= 9; d++) {
                    long w = dp[ln][mask][d];
                    if (w == 0)
                        continue;
                    if (d > 0)
                        dp[ln + 1][mask | (1 << (d - 1))][d - 1] += w;
                    if (d < 9)
                        dp[ln + 1][mask | (1 << (d + 1))][d + 1] += w;
                }
        long ans = 0;
        for (int ln = 1; ln <= maxD; ln++)
            for (int d = 0; d <= 9; d++)
                ans += dp[ln][ALL][d];
        System.out.println(ans);
    }
}