Một bài toán đến từ Bình Dương

huyhau6a2 đang chơi lật giấy. Giả sử tờ giấy là ma trận $2^x\cdot 2^y$, giá trị ở ô $(i,j)$ là $a_{i,j}$. huyhau6a2 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:

• 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.

huyhau6a2 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. huyhau6a2 sẽ chuẩn bị ba giá trị $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.

0 0 3

6