“Multidimensional spaces are completely out of style these days, unlike genetics problems” — thought physicist Woll and changed his subject of study to bioinformatics. Analysing results of sequencing he faced the following problem concerning DNA sequences. We will further think of a DNA sequence as an arbitrary string of uppercase letters “A”, “C”, “G” and “T” (of course, this is a simplified interpretation).

### Output

Output should contain a single integer — the number of strings filtered by the collection modulo $1000000009$ ($10^9 + 9$).

### Note

In the first sample, a string has to be filtered by “A”. Clearly, there is only one such string: “AA”.

In the second sample, there exist exactly two different strings satisfying the condition (see the pictures below).

### 题解

dp[i][j][k]表示已经填了i位，结尾的一位在trie中标号为j，最后的k位目前没有属于任何一个模式串的方案数。
val[i]表示以trie数上的点i为结尾，能表示的串的最大的长度。