Problem F
Train Addiction

http://clipart-library.com, Used with permission

Catherine loves toy trains. In fact, she loves them so much that her parents are starting to get worried, so Catherine spends her days and nights building toy trains when her parents are not watching. The store down the street where Catherine lives sells identical toy train sets containing $K$ different train cars of various colors and lengths. For her next big project Catherine wants to build a train of length $N$. Catherine’s toy trains are always in the form of a straight line consisting of train cars attached to each other, with a clearly designated first car, second car, and so on. Assuming Catherine always finds means of acquiring money for train sets, and the store down the street has an infinite supply of train sets, how many different trains of length $N$ can Catherine construct?


The first line of input contains an integer $T$ $(1 \leq T \leq 10)$ denoting the number of test cases that follow.

Each test case consists of one line of input. The line begins with two integers: $N$ $(1 \leq N \leq 10^9)$, the length of the train Catherine wants to construct, and $K$ $(1 \leq K \leq 500)$, the number of train cars in a train set. Following this are $K$ integers, each in the interval $[1,50]$, representing the lengths of the toy train cars found in a train set (you can assume that each train car in a set has a unique color).


For each test case output a line containing the number of distinct trains of length $N$ that Catherine can construct with her infinite supply of identical train sets. Since these numbers might be large, report each number modulo $10^9+7$. Two trains of length $N$ are considered different if one of the following holds: (a) the two trains have a different number of cars, (b) the two trains have the same number of cars, $R$, and if the cars in each train are numbered $1, 2, \ldots , R$ from front to back, then there exists some $i$ $(1 \leq i \leq R)$ such that the $i^{th}$ car in one train is a different color than the $i^{th}$ car in the other train. If Catherine is unable to construct a train of length $N$, output IMPOSSIBLE.

Sample Input 1 Sample Output 1
5 3 1 2 3
5 2 1 1
11 2 7 5

Please log in to submit a solution to this problem

Log in