Câu chuyện kể rằng...

Ngày xửa ngày xưa, Vua Tyrone Công Bằng có 4 vị bộ trưởng. Vị bộ trưởng thứ nhất (cố vấn hàng đầu của nhà vua) được trả 7 đồng vàng mỗi tuần. Vị bộ trưởng thứ hai được trả 4 đồng vàng mỗi tuần. Vị bộ trưởng thứ ba và thứ tư mỗi người được trả 6 đồng vàng mỗi tuần. Không may, một ngày nọ Tyrone vô tình để quên Danh sách Thù lao Bộ trưởng trong máy photocopy, và Danh sách này đã xuất hiện trên trang nhất của tờ báo Thời báo Vương quốc. Lúc này, vị bộ trưởng thứ hai yêu cầu được nói chuyện với nhà vua, ông ta rất buồn vì lương của mình thấp hơn lương của vị bộ trưởng thứ ba có cấp bậc thấp hơn.

Đức vua Tyrone Công Bằng thấy không còn giải pháp nào khác ngoài việc sa thải vị bộ trưởng thứ ba. Suy cho cùng, việc giảm lương của bộ trưởng thứ ba, tăng lương của bộ trưởng thứ hai, hay thay đổi chức danh công việc đều là những giải pháp không công bằng theo ý kiến của nhà vua. Và chúng ta là ai mà dám nghi ngờ Vua Tyrone? Tất nhiên, việc sa thải vị bộ trưởng thứ ba không giải quyết được vấn đề. Vị bộ trưởng thứ hai tiếp tục phàn nàn vì lương của ông ta vẫn thấp hơn lương của vị bộ trưởng thứ tư. Thế là Vua Tyrone cũng sa thải luôn vị bộ trưởng thứ tư. Tại thời điểm này, không ai trong số hai vị bộ trưởng còn lại phàn nàn, và mọi người sống hạnh phúc mãi mãi về sau.

...đợi một chút. Tôi đã kể sai rồi. Tôi xin lỗi. Trí nhớ của tôi không còn được như xưa nữa. Chờ tôi một lát... Đúng rồi. Vua Tyrone Công Bằng. Bốn bộ trưởng. Trả lương lần lượt là 7, 4, 6, và 6. À, đúng rồi. Đoạn kết là như thế này...

Khi vị bộ trưởng thứ hai phàn nàn về sự bất công, Vua Tyrone đã sa thải vị bộ trưởng thứ nhất. Một số người có thể nói điều này hơi khắc nghiệt, vì vị bộ trưởng thứ nhất không liên quan gì cả, nhưng chúng ta không nên nghi ngờ Vua Tyrone. Rõ ràng, vị bộ trưởng thứ hai vẫn phàn nàn, nên Vua Tyrone chỉ đơn giản là sa thải ông ta luôn. Trong số hai vị bộ trưởng còn lại, mỗi người đều được trả lương ít nhất bằng bất kỳ vị bộ trưởng nào dưới quyền mình, nên không ai trong số họ phàn nàn. Và mọi người sống hạnh phúc mãi mãi về sau.

Tốt hơn nhiều rồi... tôi nghĩ vậy. Có lẽ thế? Bây giờ tôi cũng không chắc nữa. Tôi biết chắc chắn rằng có \(N\) vị bộ trưởng, và tôi nhớ rõ mức lương của họ. Tôi cũng biết rằng mỗi khi lương của một bộ trưởng thấp hơn lương của một bộ trưởng đứng sau ông ta, ai đó sẽ phàn nàn, và một bộ trưởng nào đó sẽ bị sa thải; nhưng đó có thể là bất kỳ bộ trưởng nào, bất kể bộ trưởng đó có liên quan gì đến vấn đề hay không. Các bộ trưởng tiếp tục bị sa thải cho đến khi không còn ai phàn nàn vì tất cả các mức lương (của những người còn lại) tạo thành một dãy không tăng. Tại thời điểm đó, việc sa thải dừng lại. Nhưng tôi không nhớ các bộ trưởng đã bị sa thải theo thứ tự nào.

Bạn có thể giúp tôi sửa lại câu chuyện của mình không? Hoặc ít nhất hãy cho tôi biết có bao nhiêu câu chuyện khác nhau mà tôi có thể đã kể. Hai câu chuyện được coi là khác nhau nếu trình tự các bộ trưởng bị sa thải trong đó không giống nhau.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ gồm hai dòng. Dòng đầu tiên chứa một số nguyên \(N\), và dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách biểu thị mức lương của các bộ trưởng, theo thứ tự từ vị bộ trưởng thứ nhất đến vị bộ trưởng thứ \(N\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng câu chuyện tôi có thể kể cho bạn, modulo 10007.

Ràng buộc

• Mỗi mức lương sẽ là số nguyên dương và tối đa là 10000.

Phân nhóm

• Test set 1 (Visible):

  • \(1 \le T \le 100\).
  • \(1 \le N \le 100\).

  • Test set 2 (Hidden):

  • \(1 \le T \le 20\).

  • Đối với 80% số bộ test, \(1 \le N \le 2000\).
  • Đối với tất cả các bộ test, \(1 \le N \le 8000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4
7 4 6 6
8
90 80 70 60 50 50 40 30
2
7 8

Case #1: 14
Case #2: 1
Case #3: 2

Nguồn

Google Code Jam 2013, Chung kết thế giới, bài Let Me Tell You a Story.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.