Nguồn:
https://www.codechef.com
Công
chúa Rupsa thấy một người bạn đang chơi một trò chơi đặc biệt. Trò chơi diễn ra
như sau:
·
N+1 số xuất hiện tuần tự ( mỗi số tại một
thời điểm ) từ A0 đến AN.
·
Bạn phải ghi những
con số vào một tờ giấy, A0 được viết đầu tiên. Những số khác được viết
theo quy tắc quy nạp – Sau khi Ai-1 số đã được ghi trong một hàng, thì Ai
có thể được viết ở hai đầu của hàng. Nghĩa là, bạn viết A0 đầu tiên, sau
đó A1 có thể được viết ở bên trái hoặc bên phải để tạo thành A0A1
hoặc A1A0, và cứ tiếp tục như vậy.
·
Ai phải được viết trước Aj, với mọi i < j.
·
Ở bước bạn viết số
Ai (i>0), điểm số của bạn sẽ được tăng lên một lượng bằng tích
của Ai và số cạnh nó. (Chú ý rằng ở bất cứ bước nào
thì chỉ có một số duy nhất cạnh nó giống như bạn viết số
cuối cùng).
·
Tổng số điểm của
trò chơi là số điểm bạn có được sau khi viết tất cả N + 1 số.
·
Công chúa Rupsa muốn
tìm ra tổng số điểm của tất cả các cách chơi khác nhau. Hai cách chơi khác nhau
nếu sau khi viết N + 1 số, chúng ta đọc từ trái sáng phải, sẽ xuất hiện những vị
trí i mà số ở vị trí i của 2 cách chơi khác nhau. Nhưng bởi vì
công chúa đã tìm ra tình yêu đích thực của mình, một hoàng tử ếch, và rất nóng
lòng gặp hoàng tử, bạn hãy giúp công chúa giải quyết nó càng sớm càng tốt. Bởi
kết quả có thể rất lớn nên chỉ cần in kết quả lấy dư cho 109 +
7.
Dữ
liệu vào:
+ Dòng đầu tiên chứa một số tự nhiên T, thể hiện số
lượng test.
+ Dòng đầu của mỗi test chứa 1 số tự
nhiên N.
+ Dòng thứ hai chứa N + 1 số tự nhiên từ A0 đến
AN
Dữ
liệu ra:
+ Với mỗi test, in ra một dòng chứa một số là kết quả tìm được
Ràng
buộc:
+ 1 ≤ T ≤ 10
+ 1 ≤ N ≤ 105
+ 1 ≤ Ai ≤
109
Subtasks
Subtask #1: 1 ≤ N ≤ 10 (10 điểm)
Subtask #2: 1 ≤ N ≤ 1000 (20 điểm)
Subtask #3: Như ràng buộc gốc (70 điểm)
Ví
dụ:
Input:
1
1
Output:
4
Giải
thích: Có 2 cách chơi: A0A1 có số
điểm là 2 và A1A0 cũng có số điểm là 2. Do đó đáp án là 2+2=
4
