THỰC HÀNH

Trong trận lập lịch sử máy tính, hãy viết chương trình để tính toán đường đi ngắn nhất từ một ô trên bàn cờ 4×4 đến ô thứ 15 theo thứ tự các ô được đánh số từ 0 đến 15 theo hướng kim đồng hồ.

Bàn cờ được biểu diễn như sau:

     0  1  2  3
     4  5  6  7
     8  9 10 11
    12 13 14 15
    

Đường đi có thể đi qua các ô lân cận (ô nằm ngang hoặc dọc) và chỉ được phép đi theo hướng tăng dần số ô (tức là chỉ được phép đi từ ô có số nhỏ hơn đến ô có số lớn hơn). Mỗi bước đi được tính là 1 đơn vị chi phí.

Đường đi hợp lệ phải thỏa mãn các điều kiện sau:

• Bắt đầu từ ô có số nhỏ hơn hoặc bằng số đích (ô số 15).
• Chỉ được phép đi qua các ô có số tăng dần theo thứ tự từ ô xuất phát đến ô đích.
• Không được phép quay lại ô đã đi qua trước đó.

Giả sử bàn cờ ban đầu không có chướng ngại vật nào, hãy tìm đường đi ngắn nhất từ ô số 0 đến ô số 15.

Input:

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁶).
• Dòng thứ hai chứa n số nguyên aᵢ (0 ≤ aᵢ < 2¹⁶).

Các số trên mỗi dòng được cách nhau bởi dấu cách.

Output: Ghi ra kết quả là độ dài của đường đi ngắn nhất từ ô 0 đến ô 15 theo modulo 10⁹ + 7.

Chú ý:

• 50% số điểm của bài kiểm tra đều thuộc về trường hợp n ≤ 10000.

Example

Input:
3
1047 640 1632

Output:
1