Yêu cầu

Mọi người đều biết về Fibonacci, là người đã phát minh ra dãy số nổi tiếng trong đó hai số đầu tiên các số hạng là 0 và 1 và từ đó trở đi mỗi số hạng bằng tổng của hai số hạng trước đó. Điều mà hầu hết mọi người không biết là ông ta có một người anh trai hơi chậm phát triển trí tuệ tên là Tribonacci. Trong một nỗ lực tuyệt vọng để vượt qua anh trai mình và đạt được vinh quang vĩnh cửu, Tribonacci đã phát minh ra dãy số của mình: ba số hạng đầu tiên là 0, 1, 2 và từ đó trở đi mỗi số hạng là tổng của ba số trước đó.

Đáng buồn thay, bất chấp lòng dũng cảm và sự cống hiến to lớn của mình, Tribonacci không bao giờ có thể tính toán nhiều hơn hơn 3 số hạng đầu tiên của dãy. Đáng buồn hơn nữa, vào một đêm lạnh giá, ông ấy đã thực hiện một hành động phi thường, nỗ lực tinh thần làm giãn một trong những mạch máu trong não của anh ta, gây xuất huyết nghiêm trọng và giết chết ông ta ngay lập tức. Điều này được biết đến lâm sàng như chứng phình động mạch, nhưng tất nhiên Tribonacci không biết điều này ( ngay cả việc phát âm từ phình động mạch cũng là một nhiệm vụ bất khả thi đối với ông ta).

Bạn hãy viết chương trình để làm điều mà ông còn đang dang giở: tính số Tribonacci thứ n modulo 1,000,000,009.

Dữ liệu vào Specification

• Đầu vào chứa một số trường hợp thử nghiệm (tối đa 400).
• Mỗi trường hợp thử nghiệm chứa một số nguyên duy nhất N (\(1 \le N \le 10^{16}\)).
• Dòng cuối cùng của input là số 0.

Dữ liệu ra Specification

• Ghi ra số Tribonacci thứ N

Sample Input

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    100
    10000
    10000000
    100000000000
    10000000000000000
    0

Sample Output

    0
    1
    2
    3
    6
    11
    20
    37
    68
    125
    616688122
    335363379
    272924536
    48407255
    163452242