By Cristhian Bonilha, UTFPR Brazil
Andre, Bruno and Carlos are friends for a long time, and if there is something that they know about each other is how punctual they are. Andre is known to be always the last one to arrive to a meeting between the three of them, and Carlos is always the first. Bruno always arrives before Andre, but never before Carlos.
It's the end of the month and the three friends need to go to the bank to pay some bills. Including them, there are N people at the line to use the bank teller. Knowing how they are punctual between them, in how many ways the bank line can be ordered?
Remember that the rules only apply between the three of them, for example, Carlos always arrives before Bruno and Andre, but may arrive later than other people at the line. Two orderings are considered different if there is at least one person who is in a different position in each ordering.
There will be several test cases. Each test case starts with one integer N (3 ≤ N ≤ 10⁵), indicating the number of people in the file, including Andre, Bruno and Carlos.
The last test case is indicated when N = 0.
For each test case print one line, containing one integer, representing the number of ways the bank line can be ordered. As the result can be very high, print the result with rest of division in 1000000009.
|Sample Input||Sample Output|