Một bài toán đến từ Bình Dương
2^x\cdot 2^y, giá trị ở ô (i,j) là a_{i,j}. có thể thực hiện lật giấy theo một trong 4 cách: Lật trái, phải, trên, dưới. Cụ thể có thể liệt kê như sau:
đang chơi lật giấy. Giả sử tờ giấy là ma trận-
Lật dọc: Ma trận 2^x\cdot 2^y đổi thành ma trận 2^x\cdot 2^{y-1} (y>0). Có thể xem ví dụ như trên:
1 2|3 4 5 6|7 8
Việc lật này lại chia làm lật trái hoặc lật phải:- Lật trái: Với mọi giá trị i,j (1\le i\le 2^x,1\le j\le 2^{y-1}), cập nhật a_{i,2^y-j+1}=a_{i,2^y-j+1}-a_{i,j}. Sau đó, bỏ phần ma trận trái
- Lật phải: Với mọi giá trị i,j (1\le i\le 2^x,1\le j\le 2^{y-1}), cập nhật a_{i,j}=a_{i,j}-a_{i,2^y-j+1}. Sau đó, bỏ phần ma trận phải
Sau khi bỏ ma trận, y sẽ bị trừ đi 1
Hãy xét ví dụ như trong hình trên, việc lật trái làm thay đổi ma trận thành:
0 0|3-2 4-1 => 0 0|1 3 => 1 3 0 0|7-6 8-5 => 0 0|1 3 => 1 3
-
Lật ngang: Ma trận 2^x\cdot 2^y đổi thành ma trận 2^{x-1}\cdot 2^y (x>0). Có thể xem ví dụ như trên:
1 2 3 4 _______ 5 6 7 8
Việc lật này lại chia làm lật trên hoặc lật dưới:- Lật trên: Với mọi giá trị i,j (1\le i\le 2^{x-1},1\le j\le 2^y), cập nhật a_{2^x-i+1,j}=a_{2^x-i+1,j}-a_{i,j}. Sau đó, bỏ phần ma trận trên
- Lật dưới: Với mọi giá trị i,j (1\le i\le 2^{x-1},1\le j\le 2^y), cập nhật a_{i,j}=a_{i,j}-a_{2^x-i+1,j}. Sau đó, bỏ phần ma trận dưới
Sau khi bỏ ma trận, x sẽ bị trừ đi 1
Hãy xét ví dụ như trong hình trên, việc lật trên làm thay đổi ma trận thành:
0 0 0 0 => 0 0 0 0 _______________ _______ => 4 4 4 4 5-1 6-2 7-3 8-4 => 4 4 4 4
Việc lật này diễn ra đến khi ra ma trận 1\cdot 1 (tức x=y=0) thì thôi. Gọi kết quả đó là v
Gọi f(M,x,y) (với x,y là kích thước, M là ma trận cho trước kích thước 2^x\cdot 2^y) là tổng tất cả các giá trị v trong tất cả khả năng lật.
n,m,k. Các tờ giấy sẽ là tất cả ma trận M kích thước 2^n\cdot 2^m, với các giá trị nằm trong đoạn [1,k]. Tổng cộng có k^{2^{n+m}} bảng khác nhau. Nhiệm vụ của bạn là tính tổng tất cả f(M,n,m) có thể tạo được.
thấy lật giấy có một tờ thì chán quá nên sẽ chuẩn bị rất nhiều tờ giấy để lật. sẽ chuẩn bị ba giá trịInput, Output và Subtasks
Input: (FOLD.inp
)
- Gồm 3 số n,m,k (0\le n,m\le 10^{18}, 1\le k\le 10^{18})
Output: (FOLD.out
)
- In ra một số duy nhất là kết quả bài toán. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi mod\ 10^9+7
Subtasks
- Subtask 1 (25\%): n,m,k\le 2
- Subtask 2 (25\%): n,m\le 10^6
- Subtask 3 (25\%): n,m\le 10^{12}
- Subtask 4 (25\%): Không có ràng buộc gì thêm
Sample
Input (FOLD.inp
)
0 0 3
Output (FOLD.out
)
6
Note
- Có 3 ma trận M kích thước 1\cdot 1 có thể tạo ra, là
1
,2
,3
. Các ma trận trên đều kích thước 1\cdot 1 nên không phải lật gì cả. Kết quả là 1+2+3=6
Bình luận