1228B.md (2287B)
1 Source: https://codeforces.com/problemset/problem/1228/B 2 3 B. Filling the Grid 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Suppose there is a $h \times w$ grid consisting of empty or full cells. Let's make some definitions: 22 23 * $r_{i}$ is the number of consecutive full cells connected to the left side in the $i$-th row ($1 \le i \le h$). In particular, $r_i=0$ if the leftmost cell of the $i$-th row is empty. 24 * $c_{j}$ is the number of consecutive full cells connected to the top end in the $j$-th column ($1 \le j \le w$). In particular, $c_j=0$ if the topmost cell of the $j$-th column is empty. 25 26 In other words, the $i$-th row starts exactly with $r_i$ full cells. Similarly, the $j$-th column starts exactly with $c_j$ full cells. 27 28  These are the $r$ and $c$ values of some $3 \times 4$ grid. Black cells are full and white cells are empty. 29 30 You have values of $r$ and $c$. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of $r$ and $c$. Since the answer can be very large, find the answer modulo $1000000007\,(10^{9} + 7)$. In other words, find the remainder after division of the answer by $1000000007\,(10^{9} + 7)$. 31 32 Input 33 34 The first line contains two integers $h$ and $w$ ($1 \le h, w \le 10^{3}$) — the height and width of the grid. 35 36 The second line contains $h$ integers $r_{1}, r_{2}, \ldots, r_{h}$ ($0 \le r_{i} \le w$) — the values of $r$. 37 38 The third line contains $w$ integers $c_{1}, c_{2}, \ldots, c_{w}$ ($0 \le c_{j} \le h$) — the values of $c$. 39 40 Output 41 42 Print the answer modulo $1000000007\,(10^{9} + 7)$. 43 44 Examples 45 46 Input 47 48 ``` 49 3 4 50 0 3 1 51 0 2 3 0 52 ``` 53 54 Output 55 56 ``` 57 2 58 ``` 59 60 Input 61 62 ``` 63 1 1 64 0 65 1 66 ``` 67 68 Output 69 70 ``` 71 0 72 ``` 73 74 Input 75 76 ``` 77 19 16 78 16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12 79 6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4 80 ``` 81 82 Output 83 84 ``` 85 797922655 86 ``` 87 88 Note 89 90 In the first example, this is the other possible case. 91 92  93 94 In the second example, it's impossible to make a grid to satisfy such $r$, $c$ values. 95 96 In the third example, make sure to print answer modulo $(10^9 + 7)$.