Một hôm nọ, MofK được sư phụ cho mượn một binh khí đặc biệt là dãy nhị phân ~s~ để luyện tập tuyệt kĩ "thần tốc hậu tố". Với võ công cao cường, chỉ trong chốc lát MofK đã vận được dãy hậu tố ~p~ của ~s~. Tuy nhiên vì chưa thật sự thuần thục, phần nội công dư thừa của y đã đốt cháy binh khí của sư phụ. Không hề lo sợ, y ranh ma nghĩ rằng mình có thể rèn lại binh khí ~s~ từ dãy ~p~ vận được. Sau khi rèn lại dãy ~s~, MofK lại thấy không giống với dãy của sư phụ đưa cho mình, lúc này y mới thực sự hoảng hốt vì nhận ra có rất nhiều dãy ~s~ khác nhau có thể dùng để vận ra cùng một hậu tố ~p~. MofK rơi vào hoang mang...

Cho ~p~ là một hoán vị của dãy ~1, 2, 3,..., n~, hãy đếm số lượng dãy nhị phân độ dài ~n~ có dãy hậu tố (suffix array) là ~p~.

Dãy hậu tố ~p~ của một dãy nhị phân ~s~ độ dài ~n~ được định nghĩa như sau: Đặt ~t_i~ là xâu tạo được bằng cách nối các kí tự liên tiếp trong ~s~ từ vị trí ~i~ đến vị trí ~n~. Dãy ~t'~ gồm các phần tử trong ~t~ nhưng được sắp xếp theo thứ tự từ điển tăng dần, khi đó ~p_i~ là vị trí của xâu ~t'_i~ trong ~t~.

Xâu kí tự ~a~ có thứ tự từ điển nhỏ hơn xâu kí tự ~b~ nếu thỏa một trong các điều kiện sau:

+ ~a~ là tiền tố của ~b~.

+ Tồn tại một giá trị nguyên ~i~ thỏa ~a[j] = b[j]~ ~\forall 1 \leq j < i~ và ~a[i] < b[i]~.

Input

Dòng đầu tiên chứa số nguyên ~T~ (~T \leq 20~) là số bộ dữ liệu.

Trong các dòng tiếp theo, mỗi nhóm dòng miêu tả một bộ dữ liệu bao gồm:

+ Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^5~).

+ Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2,..., p_n~ biểu diễn dãy ~p~. Dữ liệu đảm bảo ~p~ là một hoán vị của dãy ~1, 2, 3, ..., n~.

Output

In ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả cho bộ dữ liệu tương ứng, chia lấy dư cho ~10^9 + 7~.

Scoring

~50\%~ số test có ~n \leq 15~ với mọi bộ dữ liệu.

~50\%~ còn lại không có ràng buộc gì thêm.

Sample Input 1

2
4
4 1 2 3
4
1 2 3 4

Sample Output 1

1
1