Отдых на море — это замечательно! Но вот программисту Паше ужасно скучно лежать на пляже в Турции. Настолько скучно, что Паша решил посчитать количество трехзначных простых чисел. Он так увлекся этим занятием, что начал изучать 3-простые числа. Так Паша называет числа, у которых любые 3 подряд идущие цифры образуют трехзначное простое число. Паша уже начал работу над теорией божественного происхождения таких чисел, когда какие-то хулиганы окатили Пашу холодной водой и стали кричать какие-то загадочные слова вроде «Sunstroke!», «Sonnenstich!» и «Colpo di sole!»

Вам предстоит продолжить дело Паши и выяснить насколько часты (или редки) 3-простые числа.

Ввод содержит целое число n (3 ≤ n ≤ 10000).

Выведите количество n-значных 3-простых чисел, вычисленное по модулю 10⁹ + 9.