# #694. 【UR #23】国王出游

### 样例一

#### input

2 3 2 0 1 1 1 2 3



#### output

748683270



#### explanation

$~$ $(1,0)$ $(-1,0)$ $(0,2)$ $(0,-3)$
$(1,0)$ $(2,1):4$ $(0,1):0$ $(1,3):27$ $(1,-2):-8$
$(-1,0)$ $(0,1):0$ $(-2,1):4$ $(-1,3):27$ $(-1,-2):-8$
$(0,2)$ $(1,3):27$ $(-1,3):27$ $(0,5):0$ $(0,0):0$
$(0,-3)$ $(1,-2):-8$ $(-1,-2):-8$ $(0,0):0$ $(0,-5):0$

### 数据范围与提示

$1$ $2000$ $2000$ $20$
$2$ $100000$ $10^9$ $1$ $20$
$3$ $100000$ $2,3$ $10$
$4$ $10^9$ $2,3$ $10$
$5$ $2$ $10$
$6$ $3$ $20$
$7$ $10$