#1445. 特殊背包问题

特殊背包问题

题目描述

有N件物品和一个体积是C\red C的背包。

需要把一些物品装到背包里使得剩下的物品无法再放入,求方案数。

每件物品有一个体积Vi\red {V_i}

输入格式

本题包含多组测试数据。

第一行输入一个整数,表示数据组数。

接下来对于每组数据的第一行是两个整数,N\red NC\red C

然后N\red N个整数Vi\red {V_i},表示每个物品的体积。

输出格式

对于每个测试数据,输出2\red 2个整数,第一个表示数据编号,第二个是题目要求的方案数。

样例

输入样例

2
6 25
8 9 8 7 16 5
30 250
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

输出样例

1 15
2 16509438

提示

40%\red {40\%}数据组数小于等于20\red {20}

100%\red {100\%}数据组数小于等于1000\red {1000}

1<=C<=1000,1<=N<=30\red {1<=C<=1000,1<=N<=30}