Đầu tiên, chúng ta cần phải tính số Fibonacci thứ ~K~ khi chia đồng dư cho ~10^3 + 7~. Chúng ta có thể sử dụng nhân ma trận để giải quyết bài toán này. Ngoài ra, dãy số Fibonacci khi chia đồng dư cho ~10^3 + 7~ sẽ tạo thành chu kì Pisano. Chúng ta có thể tính trước độ dài chu kì ~\pi(n) = 108~ như tại đây hoặc tại đây. Các bạn có thể tham khảo bài tập tương tự tại VNOJ.

Khi đó, bài toán còn lại ~2~ loại truy vấn:

• ~1~ ~L~ ~R~ ~v~: Tăng các proteins trong đoạn ~[L,R]~ tăng lên một lượng giá trị là ~v~.

• ~2~ ~L~ ~R~: Tính tổng các proteins trong đoạn ~[L,R]~.

Bài toán trên có thể giải được bằng các cấu trúc dữ liệu như Segment Tree hoặc Fenwick Tree, ... Các bạn có thể tham khảo cách làm tại đây.