Tổng các đường đi

Có $n$ ô được đánh số $1,2,\dots ,n$ từ trái sang phải. Ta đặt một robot vào một ô bất kỳ, sau đó robot phải thực hiện đúng $k$ bước di chuyển.

Mỗi bước, robot đang ở ô $i$ phải di chuyển sang ô $i-1$ hoặc ô $i+1$, với điều kiện ô đích vẫn nằm trong đoạn $[1,n]$ (robot không được đi ra ngoài).

Dãy các ô mà robot đi qua theo thứ tự (kể cả ô ban đầu) tạo thành một đường đi tốt. Gọi $c_0,c_1,\dots ,c_k$ là dãy ô của một đường đi tốt ($c_0$ là ô đặt robot, $c_t$ là ô robot đang đứng sau $t$ bước). Mỗi ô $i$ có một giá trị $a_i$. Giá trị của đường đi bằng

$$a_{c_0}+a_{c_1}+\cdots +a_{c_k}.$$

Hãy tính tổng giá trị của tất cả các đường đi tốt, lấy dư cho ${10}^9+7$. Hai đường đi tốt là khác nhau nếu ô xuất phát khác nhau, hoặc tồn tại bước $t\in [1,k]$ mà vị trí robot sau $t$ bước là khác nhau.

Ngoài ra có $q$ lần cập nhật. Mỗi lần cập nhật thay đổi giá trị của đúng một ô. Sau mỗi lần cập nhật, hãy in ra tổng giá trị mới của tất cả đường đi tốt (lấy dư ${10}^9+7$).

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $k$, $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ và $x$, nghĩa là gán $a_i:=x$.

Dữ liệu ra

In ra $q$ số nguyên, số thứ $t$ là tổng giá trị của tất cả đường đi tốt sau khi thực hiện $t$ cập nhật đầu tiên, lấy dư ${10}^9+7$.

Ràng buộc

• \leq n \leq 5000$;$1 \leq k \leq 5000$;$1 \leq q \leq 2 \cdot 10^5$.
• \leq a_i \leq 10^9$.
• Trong mỗi cập nhật: $1\le i\le n$, $1\le x\le {10}^9$.

Ví dụ