Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P183PROG - ROUND 3G - Trừ và Cộng

Cho dãy số nguyên a gồm n phần tử a1, a2, …, an (ai ≠ 0). Nhiệm vụ của bạn là đếm số cách đổi dấu của các phần tử trong dãy (có thể đổi dấu một phần tử từ âm thành dương và ngược lại, hoặc để nguyên) sao cho tổng các phần tử có giá trị là M.

Input

Dòng đầu gồm 1 số nguyên dương T (T ≤ 20) là số lượng bộ test.

Các dòng tiếp theo là T bộ test. Mỗi bộ test có dạng như sau:

  • Dòng đầu tiên gồm 2 số nguyên n, M (1 ≤ n ≤ 100, |M| ≤ 107).
  • Dòng tiếp theo gồm n số nguyên a1, a2, …, an (ai ≠ 0, |ai| ≤ 1000).

Output

Gồm T dòng, mỗi dòng là kết quả của một bộ test – số cách đổi dấu các phần tử để tổng của chúng là M, modulo 109 + 7 (lấy phần dư trong phép chia kết quả cho 109 + 7).

Example

Input:
2
3 0
1 1 2
3 0
1 1 1 Output: 2
0
Giải thích:
Với bộ test thứ 1, ta có 2 cách đổi là -1 -1 2 và 1 1 -2.
Với bộ test thứ 2, ta không có cách đổi nào để tổng các phần tử bằng 0.

Được gửi lên bởi:Admin
Ngày:2018-03-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.