{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Trong một cửa hàng kỳ lạ có **n** loại đồng xu có mệnh giá **A\u003csub\u003e1\u003c/sub\u003e, A\u003csub\u003e2\u003c/sub\u003e ... A\u003csub\u003en\u003c/sub\u003e**. **C\u003csub\u003e1\u003c/sub\u003e, C\u003csub\u003e2\u003c/sub\u003e, ... C\u003csub\u003en\u003c/sub\u003e** biểu thị số lượng đồng xu có mệnh giá **A\u003csub\u003e1\u003c/sub\u003e, A\u003csub\u003e2\u003c/sub\u003e ... A\u003csub\u003en\u003c/sub\u003e** tương ứng. Bạn cần tìm số cách để tạo ra số **K** bằng các đồng xu.\n\nVí dụ, giả sử có ba đồng xu 1, 2, 5 và chúng ta có thể sử dụng đồng xu 1 tối đa 3 lần, đồng xu 2 tối đa 2 lần và đồng xu 5 tối đa 1 lần. Khi **K \u003d 5** thì các cách có thể là:\n\n(1, 1, 1, 2)\n\n(1, 2, 2)\n\n(5)\n\nVậy, số 5 có thể tạo ra được trong 3 cách."}},{"title":"Input","value":{"format":"MD","content":"Input bắt đầu bằng một số nguyên **T (\u0026#8804; 100)**, đại diện cho số lượng bài toán.\n\nMỗi bài toán bắt đầu bằng một dòng chứa hai số nguyên **n (1 \u0026#8804; n \u0026#8804; 50)** và **K (1 \u0026#8804; K \u0026#8804; 1000)**. Dòng tiếp theo chứa **2n** số nguyên, biểu thị **A\u003csub\u003e1\u003c/sub\u003e, A\u003csub\u003e2\u003c/sub\u003e ... A\u003csub\u003en\u003c/sub\u003e, C\u003csub\u003e1\u003c/sub\u003e, C\u003csub\u003e2\u003c/sub\u003e ... C\u003csub\u003en\u003c/sub\u003e (1 \u0026#8804; A\u003csub\u003ei\u003c/sub\u003e \u0026#8804; 100, 1 \u0026#8804; C\u003csub\u003ei\u003c/sub\u003e \u0026#8804; 20)**. Tất cả các **A\u003csub\u003ei\u003c/sub\u003e** sẽ là khác nhau."}},{"title":"Output","value":{"format":"MD","content":"Đối với mỗi bài toán, in ra số thứ tự bài toán và số cách tạo ra số **K**. Kết quả có thể lớn, vì vậy, in ra kết quả theo modulo **100000007**."}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 5\n1 2 5 3 2 1\n4 20\n1 2 3 4 8 4 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3\nCase 2: 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}