D. AVERAGE

Cho dãy số . Hãy đếm số lượng dãy con (có ít nhất một phần tử, có thể không liên tiếp) có trung bình cộng (tổng giá trị các phần tử chia cho số lượng phần tử) đúng bằng .

Vì đáp án có thể rất lớn nên bạn được yêu cầu đưa ra phần dư của số lượng dãy con sao khi chia cho .

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương – số bộ dữ liệu vào. Mỗi bộ dữ liệu vào có định dạng như sau:
  • Dòng thứ nhất ghi hai số nguyên – số phần tử của dãy số và giá trị trên đề bài.
  • Dòng thứ hai ghi số nguyên dương mô tả dãy số.

Dữ liệu ra:

• Với mỗi bộ dữ liệu, in ra trên một dòng kết quả tương ứng (chia cho lấy phần dư).

Ví dụ:

Dữ liệu vào:

3
4 6
5 7 6 7
5 100
4 2 5 10 5
6 100
77 97 114 105 115 97

Dữ liệu ra:

5
0
1

Giải thích

• Ở ví dụ thứ nhất, các dãy con cần đếm là
  • .
• Ở ví dụ thứ hai, các dãy con đều có trung bình cộng nhỏ hơn .
• Ở ví dụ thứ ba, dãy con duy nhất cần đếm là: .

Giới hạn:

• Subtask ;
• Subtask ;
• Subtask Không có ràng buộc gì thêm.