The Psychology prof from the HSS Department has gone psycho! While grading the mid-sem copies, he thought of a new scheme of awarding marks to the descriptive answers; by weighing the strings.

The mass of a string s can be computed as follows: for each letter that occurs at least once in s, its leftmost and rightmost occurrences le and ri are found and the weight is increased by ri-le.

If s="abca", the weight of s is (3-0) + (1-1) + (2-2) = 3. (The leftmost occurrence of 'A' is at the index le=0, the rightmost one is at ri=3, so 'A' contributes 3-0 = 3 to the weight of s. 'B' and 'C' contribute 0

Given an integer l. Consider all strings of length l. Compute the weight of each of these strings. The strings with the minimum weight among all possible are called Chotu strings. Your task is to count the number of Chotu-strings of length L. Output the answer modulo 1,000,000,009.

For an answer of length l, the Psycho prof. will use your answer as cutoff for grading the answer. Help him calculate the cutoff.

NOTE: Strings have characters 'a'-'z'.

INPUT:

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each case contains a single line having the integer L.

OUTPUT:

For each test case, output a single line containing the number of light-weight strings of length L modulo 1,000,000,009.

CONSTRAINTS:

1<=T<=1000

1<=L<=1000

PROBLEM SETTER: Sparsh Kumar Sinha