Compositions

A *composition* of an integer
$n$ is an ordered set of
integers which sum to $n$.
Two *compositions* with the same elements
but in different orders are considered different (this
distinguishes *compositions* from
partitions). For example, all the *compositions* of the first few integers are:

1: {1} 2: {1+1, 2} 3: {1+1+1, 1+2, 2+1, 3} 4: {1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1, 4}

Note that `1+2` and `2+1` each count as distinct *compositions* of `3`. As
you may have suspected, there are $2^{(n-1)}$ *compositions* of $n$.

In this problem, we set conditions on the elements of the
*compositions* of $n$. A *composition* misses a set $S$ if no element of the *composition* is in the set $S$. For example, the *compositions* of the first few integers which miss
the set of even integers are:

1: {1} 2: {1+1} 3: {1+1+1, 3} 4: {1+1+1+1, 1+3, 3+1}

No odd integer can have a *composition*
missing the set of odd integers and any *composition* of an even integer consisting of only
even integers must be $2$
times a *composition* of $n/2$.

For this problem you will write a program to compute the
number of *compositions* of an input
integer $n$ which miss the
elements of the arithmetic sequence $\{ m + i \cdot k \ | \ i = 0,1,\ldots \}
$.

The first line of input contains a single decimal integer $P$, ($1 \le P \le 60$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by the three space separated integers $n$, $m$ and $k$ with $1 \le n \le 30$ and $0 \le m < k < 30$.

For each data set there is one line of output. The single
output line consists of the data set number, $K$, followed by a single space
followed by the number of *compositions*
of $n$ which miss the
specified sequence.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 10 0 2 2 15 1 4 3 28 3 7 |
1 55 2 235 3 18848806 |