Cho một lớp Flower gồm các thuộc tính: giá trị sắc đẹp và giá trị mùi hương, gồm các phương thức như: thay đổi giá trị sắc đẹp và mùi hương, in ra các giá trị đó. Cho 5 lớp hoa: hoa hồng, hoa ly, hoa lan, hoa tualip, hoa mai. Bạn có \(n\) chậu cây, bạn cần trồng 1 trong 5 loại hoa trên vào mỗi chậu cây, mỗi lớp hoa kể trên kế thừa các thuộc tính và phương thức của lớp Flower. Nhưng mỗi lớp hoa còn có những ràng buộc riêng của chính nó:

• Hoa Hồng chỉ được trông ngay sau hoa Ly
• Hoa Ly chỉ được trồng liền sau hoa Hồng hoặc hoa Mai
• Hoa Mai không được trồng liền ngay sau hoa Mai
• Hoa Lan chỉ được trồng liền ngay sau hoa Mai hoặc hoa Tulip
• Hoa Tulip chỉ được trồng liền ngay sau hoa hồng

Hưng định nghĩa hoa hồng là loại hoa có giá trị sắc đẹp lớn nhất, hoa Ly là loại hoa có giá trị mùi hương lớn nhất (sau khi đã loại trừ hoa hồng, nên nếu hoa hồng vừa có giá trị sắc đẹp và mùi hương lớn nhất, hoa ly sẽ mang giá trị mùi hương thứ 2). Tương tự, hoa Mai là loại hoa có giá trị sắc đẹp nhỏ nhất, hoa Tulip là loại hoa có giá trị mùi hương nhỏ nhất. Hoa Lan sẽ là loại hoa còn lại. (Dữ liệu đảm bảo sẽ kh có 2 loại hoa nào trùng nhau về giá trị sắc đẹp và mùi hương).

Là một người cũng rất thích toán, Hưng muốn đếm số cách trồng hoa vào chậu sao cho không vi phạm các ràng buộc trên. Bạn hãy giúp Hưng nhé.

INPUT FORMAT

• Dòng đầu tiên chứa số nguyên \(n\) \( (1 ≤ n ≤ 10^{15}) \) là số lượng chậu hoa mà Hưng có.
• 5 dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(a_i\), \(b_i\) \( (1 ≤ a_i, b_i ≤ 10^9) \) là giá trị sắc đẹp và mùi hương của loại hoa thứ \(i\).
• Tiếp theo là các truy vấn, mỗi truy vấn thuộc một trong 2 loại:
• Nếu người dùng bấm nút \(U\), nhập số từ bàn phím \(1->5\) để chọn loại hoa cần sửa, sau đó nhập giá trị sắc đẹp và mùi hương mới của loại hoa đó.
• Nếu người dùng bấm nút \(Q\), in ra số cách trồng hoa vào chậu sao cho không vi phạm các ràng buộc trên. Chỉ có 1 truy vấn \(Q\) và đó là truy vấn cuối cùng.

OUTPUT FORMAT

• In ra số cách trồng hoa vào chậu sao cho không vi phạm các ràng buộc trên. Lưu ý, vì kết quả có thể rất lớn, bạn cần in ra kết quả theo modulo \(10^9+7\).

Ví dụ:

Input

1
1 2
2 3
3 4
5 6
6 7
1
Q

Output

5

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House