1, 2, 3 Sum 6

Interview

Time limit1sMemory limit512 MB

Summary
Count the compositions of n into parts 1, 2, and 3 that read the same forwards and backwards, modulo 1,000,000,009.
Level

Medium6 of 10

Topics
Dynamic programming, Combinatorics, Math, Prefix sum
Solved
No attempts yet

Problem

There are 3 ways to express the integer 4 as a sum of 1, 2, and 3. A sum must use at least one number. The sum must also be symmetric.

  • 1+1+1+1
  • 1+2+1
  • 2+2

Given an integer n, write a program to find the number of ways to express n as a sum of 1, 2, and 3.

Input

The first line gives the number of test cases T. Each test case occupies one line and gives an integer n. n is a positive integer and is at most 100,000.

Output

For each test case, print the number of ways to express n as a sum of 1, 2, and 3, modulo 1,000,000,009.

Examples1

  1. Example 1

    Input
    3
4
7
10
    Expected output
    3
6
20