Coins Exhibition
Contest: Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round)
Difficulty rating: 2900
Tags: data structures, dp, math

Arkady and Kirill visited an exhibition of rare coins. The coins were located in a row and enumerated from left to right from 1 to k, each coin either was laid with its obverse (front) side up, or with its reverse (back) side up.

Arkady and Kirill made some photos of the coins, each photo contained a segment of neighboring coins. Akrady is interested in obverses, so on each photo made by him there is at least one coin with obverse side up. On the contrary, Kirill is interested in reverses, so on each photo made by him there is at least one coin with its reverse side up.

The photos are lost now, but Arkady and Kirill still remember the bounds of the segments of coins each photo contained. Given this information, compute the remainder of division by 109 + 7 of the number of ways to choose the upper side of each coin in such a way, that on each Arkady's photo there is at least one coin with obverse side up, and on each Kirill's photo there is at least one coin with reverse side up.

Input format:
The first line contains three integers k, n and m (1 ≤ k ≤ 109, 0 ≤ n, m ≤ 105) — the total number of coins, the number of photos made by Arkady, and the number of photos made by Kirill, respectively.

The next n lines contain the descriptions of Arkady's photos, one per line. Each of these lines contains two integers l and r (1 ≤ l ≤ r ≤ k), meaning that among coins from the l-th to the r-th there should be at least one with obverse side up.

The next m lines contain the descriptions of Kirill's photos, one per line. Each of these lines contains two integers l and r (1 ≤ l ≤ r ≤ k), meaning that among coins from the l-th to the r-th there should be at least one with reverse side up.

Output format:
Print the only line — the number of ways to choose the side for each coin modulo 109 + 7 = 1000000007.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the following ways are possible ('O' — obverse, 'R' — reverse side):

- OROOR,
- ORORO,
- ORORR,
- RROOR,
- RRORO,
- RRORR,
- ORROR,
- ORRRO.

In the second example the information is contradictory: the second coin should have obverse and reverse sides up at the same time, that is impossible. So, the answer is 0.

Example input:
5 2 2
1 3
3 5
2 2
4 5

Example output:
8

Example input:
5 3 2
1 3
2 2
3 5
2 2
4 5

Example output:
0

Editorial:
Denote obverse-up coin as 0 and reverse-up coin as 1. Then we are to compute the number of binary strings of length k such that n of the given segments have atleast one 0 and other m ones — atleast one 1.
Let dp[i][l0][l1] be the number of binary strings of length i such that the last zero is at position l0, the last one is at l1 and all restrictions are satisfied for all segments with right borders not exceeding i. The transitions then are straighforward: check all possible values for position i + 1 and relax l0 and l1 accordingly. Let the new values be l0' and l1'. Now consider all segments ending at i + 1. If there are such [l, r] among them demanding zero while l > l0' or demanding one while l > l1', this continuation doesn't suit. Otherwise add dp[i][l0][l1] to dp[i + 1][l0'][l1']. This works in O(k3 + n + m) if we precompute all segments ending in r for all r. Anyway, this is too slow.
The first thing to enhance is to notice that either l0 = i or l1 = i. Then we have to deal with dp0[i][l1] (implying l0 = i) and dp1[i][l0] (implying l1 = i). The transitions are the same, and the complexity becomes O(k2 + n + m). Still too slow :(
The further improvement is that all positions with no segments endings can be treated similarly since the transitions are equal. At the same time it doesn't matter whether the last zero is at l0 or l0 + 1 if there are no segments beginning at l0 + 1. Same applies to l1. Let's compress coordinates then, i.e. find all xi such that xi and xi + 1 are covered by different sets of segments.
Now it's time to slightly change the dp definition: let dp0[i][l1]be the number of binary strings of length xi such that the last digit is 0, the last 1 is somewhere between xl1 - 1 + 1 and xl1 and all restrictions are satisfied for all segments with endings not exceeding xi. dp1[i][l0] is denoted in a similar fashion.
Consider the possible transitions. Without loss of generality we'll account for transitions from dp0[i][l1] to some dp?[i + 1][?]. The goal is to somehow append a binary string of length (xi + 1 - xi) to the existing one. There are three major cases:
• All additional digits are 0, then we jump to dp0[i + 1][l1] with coefficient 1 (there's only one way to construct a string of zeros).
• All additional digits are 1, then we jump to dp1[i + 1][i] with coefficient 1. Note that the last zero remains at xi.
• There are some 0 and some 1. Then the jump is to dp0[i + 1][i + 1] and dp1[i + 1][i + 1] with coefficients equal to 2xi + 1 - xi - 1 - 1 since only the last digit if fixed. This is possible iff xi + 1 - xi > 1.
Moreover, we have to consider all segments ending at xi + 1 and discard those not satisfying the restrictions. This works in $${ \mathcal { O } } ( ( n + m ) ^ { 2 } \cdot \log { ( k ) } )$$ (extra logarithm is for fast powers).
There's only one step left to a full solution. Note that in the dp above you can separate digit-adding from constraint-accounting transitions and treat them one after another. That means that you can first apply all transitions from $$dp_{*}[i]^{*}$$ to $$dp_{*}^{[i+1]}[*]$$ disregarding segments endings at xi + 1 and then null dp0[i + 1][l1], where l1 < l, where [l, xi] is an arbitrary segment applying 1-constraint and null dp1[i + 1][l0], where l0 < l, where [l, xi] is an arbitrary segment applying 0-constraint. Futhermore note that transitions with coeffitients not equal to 1 are applied only to $$dp_{*}^{[i+1][i]}$$ and $$dp_{*}^{[i+1][i+1]}$$ while values of $$dp_{*}^{i+1|j}$$ where j < i are either $$dp_{*}^{[i][j]}$$ or 0. That means we can store two arrays dp0[l1] and dp1[l0], implying i being equal to the current value. Now when jumping from i to i + 1 we have to relax $$dp_{*}^{[i]}$$ and $$dp_{*}^{[i+1]}$$, and null some prefix of dp0 and some prefix of dp1 depending on beginnins of segments ending at xi. The new values of $$dp_{*}^{[i]}$$ and $$dp_{*}^{[i+1]}$$ are easy to obtain via sum of elements in this arrays and xi + 1 - xi. With a properly chosen data structure the complexity becomes $${ \mathcal { O } } \left( ( n + m ) \log \left( n + m \right) \log \left( k \right) \right)$$ with O(n + m) memory. This is now enough to get ac.
There's an alternative approach: you can just keep track of the first non-nulled element since it can only increase. This also helps maintain the current sum of values without using specific data structures. This works in $$O((n+m)\cdot(\log(n+m)+\log(k)))$$ (including sort).