Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P197PROH - Problem H - Aki và công thức truy hồi

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:

  • F0 = b0, F1 = b1, …, Fm-1 = bm-1.
  • Với i ≥ m, Fi = c1 * Fi-1 + c2 * Fi-2 + … + cm * Fi-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ị Ai 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ị FA_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 (109 + 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 c1, c2, …, cm (0 ≤ ci ≤ 109).

Dòng thứ ba chứa m só nguyên b0, b1, …, bm-1 (0 ≤ bi ≤ 109).

Dòng thứ tư chứa hai số nguyên n và q (1 ≤ n, q ≤ 105) - 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 ≤ 109).

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 (109 + 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

Được gửi lên bởi:adm
Ngày:2019-03-30
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.