problem link: http://lightoj.com/volume_showproblem.php?problem=1345
how dp can be used to solve this problem ?
problem statement : It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the fifth mystery.
After defeating the Genie in 'Game of Bracelets', Aladdin moved forward and found a garden. There were n small Genies in the garden and they were all sad. Aladdin asked them about the lamp. But none of them was interested. So, Aladdin had to make them happy. Soon he noticed that height of every Genie is distinct but they were standing in a line randomly. Aladdin found a book there, and after reading the book, he discovered that the only way to make them happy was to make a line with the Genies such that k consecutive genies in the line could be found whose heights are in increasing order. But the book also mentioned that if k+1 consecutive Genies found in the line whose heights are in increasing order then they would be sad again. So, Aladdin did make them happy, and they showed the path to Aladdin and he moved forward.
Now you are given n and k, your task is to find in how many ways Aladdin could make them happy.
Input Input starts with an integer T (≤ 1275), denoting the number of test cases.
Each case starts with a line containing two integers: n and k (1 ≤ k ≤ n ≤ 50).
Output For each case, print the case number and the number of ways Aladdin could make them happy. As the result can be big; print the result modulo 1000 000 007.
Sample Input 5
2 2
3 2
4 3
5 4
5 3 Output for Sample Input Case 1: 1
Case 2: 4
Case 3: 6
Case 4: 8
Case 5: 41
