SP2963 PAINTBLC - Painting Blocks (Act II)

_n_ blocks are put in a line. You have _k_(1

Input consists of multiple test cases, the number of them (

For each test case, output one line with an integer, the number of ways modulo 1000000007.