Displaying Da Vinci work
The King of Florence is going to visit Da Vinci in his workshop to see his paintings. In preparation of that, Da Vinci has painted a total of N paintings that he would display to the King.
Since, the King is very busy dealing with the after effects of war, he has asked Da Vinci to make
sure that he can see all of his paintings in one standing. To solve that problem, Da Vinci has
done the following:
He has manufactured N tables, each one of a different height. He plans to keep tables in a
row and display a painting at the top of each table. This way, the King will be able to see all
the paintings when he is standing in front of this row of tables. All the paintings are of equal
This plan of Da Vinci was perfect but he received the news of another rebellion in Florence.
He knows that since King has promised to see Da Vinci’s work, he won’t back down. Da Vinci
does not want to hold the King for too long and now has decided that he will only show K of
his paintings to the King. For that, he will re-arrange the tables so that the King can only see
K of his paintings when he is standing at the front of the row. King can see a painting if there
is no painting in front of it in the row, which is blocking King’s view. Da Vinci will not remove
any tables, because if King decides that he wants to look at more of Da Vinci’s work, he wants
to be able to show it without adding anymore delay.
All of Da Vinci’s paintings are the best in the world, so he knows he can choose any of his
K paintings to display to the King. Help Da Vinci in finding in how many ways he can arrange
the table so that only K of his paintings are visible to the King.
The first line of the input contains an integer T which is the number of test cases to follow.
Then T lines follow, each containing two space separated integers N and K.
For each of the test cases, print the total number of ways Da Vinci can make them sit in a row.
Since this number can be very large, output it modulo 1000000007.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ T ≤ 501501
- 1 ≤ N ≤ 1000
- 1 ≤ K ≤ 1000
Input: 3 2 1 2 2 4 2 Output: 1 1 11
|Time Limit:||7 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions