Ciel and Genjiko
All submissions for this problem are available.
Genjiko is one of the Japanese traditional games.
Chef Ciel will take place a variant version of genjiko in her restaurant.
The rules of the game are the following:
- The challenger must be blindfolded.
- Ciel feeds the challenger one of the N foods menus of her restaurant, M times.
- The challenger must answer whether the i-th food and the j-th food are same or not, for all 1 ≤ i < j ≤ M.
- For making the game difficult, Ciel cannot use the same menu for both the i-th menu and the (i+j)-th menu for all 1 ≤ j ≤ K. (The challenger knows this)
Ciel wonders how many patterns can be the challenger's answer.
Your task is calculating the number of the patterns modulo 1000000009 (109+9).
The first line contains an integer T, the number of test cases.
Then T test cases follow.
Each test case has 3 integers N, M and K.
Print the number of the patterns of the possible answers modulo 1000000009 (109+9).
1 ≤ T ≤ 100
1 ≤ N ≤ 200
1 ≤ M ≤ 1000000000 (109)
0 ≤ K ≤ 200
5 200 5 0 2 3 1 2 3 0 3 3 1 1 1000000000 200
52 1 4 2 0
The first case is the same as genjiko.
In the traditional game genjiko, we make connections between each possible answer and the name of a book of The Tale of Genji.
However The Tale of Genji is composed of 54 books, so the names of the first book and the last book are unused.
Let the letters A, B, C, ... denote the N menus, and let "ABA" mean that Ciel uses A for the 1st food, and uses B for the 2nd food, and uses A for the 3rd food.
In the second case, Ciel cannot use the same menu consecutively.
So Ciel can use only 2 patterns "ABA" and "BAB".
However there is only one possible answer [1st ≠ 2nd, 1st = 3rd, 2nd ≠ 3rd].
In the third case, Ciel can use 8 patterns "AAA", "AAB", "ABA", "ABB", "BAA", "BAB", "BBA" and "BBB".
And there are four possible answers [1st = 2nd, 1st = 3rd, 2nd = 3rd], [1st = 2nd, 1st ≠ 3rd, 2nd ≠ 3rd], [1st ≠ 2nd, 1st = 3rd, 2nd ≠ 3rd] and [1st ≠ 2nd, 1st ≠ 3rd, 2nd ≠ 3rd].
In the fifth case, Ciel can use no patterns.
|Tags||cook20, laycurse, medium|
|Time Limit:||0.160883 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions