«Многомерные пространства нынче не в моде, а вот генные алгоритмы — очень даже», — подумал физик Воль и переквалифицировался в биоинформатика. Исследуя любезно предоставленные ему результаты секвенирования, он столкнулся со следующей задачей, касающейся цепочек ДНК. Далее мы будем считать, что цепочка ДНК — это произвольная строка, состоящая из заглавных букв «A», «C», «G» и «T» (разумеется, это упрощенная интерпретация).

Пусть есть длинная цепочка ДНК w и набор s₁, s₂, ..., s_m коротких цепочек. Будем говорить, что набор фильтрует w, если цепочками набора можно покрыть w. Естественно, подстроки для разных позиций могут пересекаться между собой и даже накрывать друг друга. Формально это условие означает следующее: пусть строка w имеет длину |w|, ее символы пронумерованы от 1 до |w|, и для каждой позиции i в строке w найдется такая пара индексов l, r (1 ≤ l ≤ i ≤ r ≤ |w|), что подстрока w[l ... r] является элементом набора s₁, s₂, ..., s_m.

Воль заметил, что цепочек фиксированной длины, фильтрующихся конкретным набором, может быть очень много, и как посчитать их количество — не знает. Помогите физику! Ваша задача — для заданной длины n и набора {s_i} найти количество различных цепочек ДНК длины n, фильтрующихся данных набором.

Ответ может быть очень большим, поэтому выведите его по модулю 1000000009.