using System;
using System.Collections.Generic;
using System.Linq;

namespace ThreeprimeNumbers
{
    public static class IntExtensions
    {
        public static bool IsPrime(this int number)
        {
            for (var divisor = 2; divisor < number; divisor++)
                if (number % divisor == 0)
                    return false;
            return true;
        }
    }
    internal static class Solver
    {
        private static Func<IEnumerable<int>> ThreeDigitPrimeNumbers =
            () => Enumerable.Range(100, 900).Where(number => number.IsPrime());
        private static Dictionary<int, IEnumerable<int>> PrefixCorrespondance(IEnumerable<int> primeNumbers)
        {
            return primeNumbers
                .GroupBy(number => number / 10)
                .ToDictionary(group => group.Key, group => group.Select(item => item));
        }
        internal static long Solve(int digitCount)
        {
            var table = new long[digitCount - 2, 90];
            var prefixes = PrefixCorrespondance(ThreeDigitPrimeNumbers());
            for (var counter = 10; counter < 100; counter++)
                table[0, counter - 10] = (prefixes.TryGetValue(counter, out var collection)) ? collection.Count() : 0;
            for (var counter = 1; counter <= digitCount - 3; counter++)
                foreach (var pair in prefixes)
                    foreach (var primeNumber in pair.Value)
                    {
                        var suffix = primeNumber % 100 - 10;
                        table[counter, pair.Key - 10] += (suffix < 0) ? 0 : table[counter - 1, suffix];
                        table[counter, pair.Key - 10] %= 1000000009;
                    }
            long sum = 0;
            for (var counter = 0; counter < 90; counter++)
                sum = (sum + table[digitCount - 3, counter]) % 1000000009;
            return sum;

        }
        public static void Main()
        {
            int.TryParse(Console.ReadLine(), out int digitCount);
            Console.Write(Solve(digitCount));
        }
    }
}