CF283C Coin Troubles

In the Isle of Guernsey there are $ n $ different types of coins. For each $ i $ $ (1

The first line contains three space-separated integers, $ n,q $ and $ t $ $ (1

A single integer, the number of valid coin combinations that Bessie could have, modulo $ 1000000007 $ $ (10^{9}+7) $ .

For the first sample, the following 3 combinations give a total of 17 cents and satisfy the given conditions: $ {0 of type 1,1 of type 2,3 of type 3,2 of type 4},{0,0,6,1},{2,0,3,1} $ . No other combinations exist. Note that even though 4 occurs in both $ b_{i} $ and $ c_{i}, $ the problem conditions are still satisfied because all $ b_{i} $ are distinct and all $ c_{i} $ are distinct.