«Многомерные пространства нынче не в моде, а вот генные алгоритмы — очень даже», — подумал физик Воль и переквалифицировался в биоинформатика. Исследуя любезно предоставленные ему результаты секвенирования, он столкнулся со следующей задачей, касающейся цепочек ДНК. Далее мы будем считать, что цепочка ДНК — это произвольная строка, состоящая из заглавных букв «A», «C», «G» и «T» (разумеется, это упрощенная интерпретация).
Пусть есть длинная цепочка ДНК w и набор s1, s2, ..., sm коротких цепочек. Будем говорить, что набор фильтрует w, если цепочками набора можно покрыть w. Естественно, подстроки для разных позиций могут пересекаться между собой и даже накрывать друг друга. Формально это условие означает следующее: пусть строка w имеет длину |w|, ее символы пронумерованы от 1 до |w|, и для каждой позиции i в строке w найдется такая пара индексов l, r (1 ≤ l ≤ i ≤ r ≤ |w|), что подстрока w[l ... r] является элементом набора s1, s2, ..., sm.
Воль заметил, что цепочек фиксированной длины, фильтрующихся конкретным набором, может быть очень много, и как посчитать их количество — не знает. Помогите физику! Ваша задача — для заданной длины n и набора {si} найти количество различных цепочек ДНК длины n, фильтрующихся данных набором.
Ответ может быть очень большим, поэтому выведите его по модулю 1000000009.
Примечание
В первом примере строка должна фильтроваться символом «A». Ясно, что такая строка единственна: «AA».
Во втором примере существуют ровно две различные строки, удовлетворяющие условию (см. картинки).
