Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Với sự đam mê bẩm sinh về Toán, thật không khó hiểu khi Aki luôn nghĩ ra những ý tưởng độc đáo.

Anh đã nghĩ ra một dãy số F có tính chất sau:

• F₀ = b₀, F₁ = b₁, …, F_m-1 = b_m-1.
• Với i ≥ m, F_i = c₁ * F_i-1 + c₂ * F_i-2 + … + c_m * F_i-m.

Đồng thời, anh có một mảng số A gồm n phần tử, ban đầu tất cả đều bằng 0. Và anh sẽ thực hiện q truy vấn trên mảng số, mỗi truy vấn thuộc 1 trong 2 loại sau:

• “1 l r x” → truy vấn này tăng tất cả các giá trị A_i với l ≤ i ≤ r thêm x đơn vị.
• “2 l r” → truy vấn này tính tổng tất cả các giá trị F_{A_i} với l ≤ i ≤ r. Do giá trị này rất lớn nên đáp số tìm được sẽ chia lấy dư cho (10⁹ + 7).

Nhưng vì quá bận bịu với những projects của chính mình nên anh ta cũng không còn cả thời gian để ngồi tính toán dải truy vấn mà mình viết ra nữa! :<

Input

Dòng đầu tiên chứa một số nguyên m (2 ≤ m ≤ 4) - độ dài truy hồi của dãy F.

Dòng thứ hai chứa m só nguyên c₁, c₂, …, c_m (0 ≤ c_i ≤ 10⁹).

Dòng thứ ba chứa m só nguyên b₀, b₁, …, b_m-1 (0 ≤ b_i ≤ 10⁹).

Dòng thứ tư chứa hai số nguyên n và q (1 ≤ n, q ≤ 10⁵) - lần lượt là kích thước của mảng A và số truy vấn mà Aki cần thực hiện.

q dòng tiếp theo, mỗi dòng thể hiện mỗi truy vấn:

Nếu là truy vấn loại 1, dòng đó gồm 4 số nguyên t, l, r, x (t = 1, 1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 10⁹).

Nếu là truy vấn loại 2, dòng đó gồm 3 số nguyên t, l, r (t = 2, 1 ≤ l ≤ r ≤ n).

Input bảo đảm có ít nhất một truy vấn loại 2.

Output

Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là kết quả mà truy vấn đó yêu cầu, chia lấy dư cho (10⁹ + 7).

Example

Input:
2
1 1
0 1
5 6
1 1 5 1
1 3 3 1
2 1 5
1 2 4 2
2 2 4
2 1 5

Output:
5
7
9