Coins Exhibition

Arkady and Kirill는 희귀 동전 전시회를 방문했다. 동전들은 한 줄로 놓여 있었고 왼쪽에서 오른쪽으로 1부터 k까지 번호가 매겨져 있었으며, 각 동전은 앞면이 위로 향하거나 뒷면이 위로 향하도록 놓여 있었다.

Arkady and Kirill는 동전 사진을 몇 장 찍었으며, 각 사진에는 서로 이웃한 동전들의 구간이 담겨 있었다. Arkady는 앞면에 관심이 있으므로, 그가 찍은 각 사진에는 앞면이 위로 향한 동전이 적어도 하나 있다. 반대로 Kirill은 뒷면에 관심이 있으므로, 그가 찍은 각 사진에는 뒷면이 위로 향한 동전이 적어도 하나 있다.

사진은 현재 사라졌지만, Arkady and Kirill는 각 사진에 담긴 동전 구간의 경계를 아직 기억한다. 이 정보가 주어질 때, Arkady가 찍은 각 사진에는 앞면이 위로 향한 동전이 적어도 하나 있고 Kirill이 찍은 각 사진에는 뒷면이 위로 향한 동전이 적어도 하나 있도록 각 동전에서 위로 향할 면을 선택하는 방법의 수를 109 + 7로 나눈 나머지를 계산한다.

첫 번째 줄에는 세 정수 k, n, m (1 ≤ k ≤ 109, 0 ≤ n, m ≤ 105)가 주어진다. 각각 전체 동전의 수, Arkady가 찍은 사진의 수, Kirill이 찍은 사진의 수를 나타낸다.

다음 n개의 줄에는 한 줄에 하나씩 Arkady가 찍은 사진에 대한 설명이 주어진다. 각 줄에는 두 정수 l와 r (1 ≤ l ≤ r ≤ k)가 주어지며, 이는 l-th번째 동전부터 r-th번째 동전까지 중 앞면이 위로 향한 동전이 적어도 하나 있어야 한다는 뜻이다.

다음 m개의 줄에는 한 줄에 하나씩 Kirill이 찍은 사진에 대한 설명이 주어진다. 각 줄에는 두 정수 l와 r (1 ≤ l ≤ r ≤ k)가 주어지며, 이는 l-th번째 동전부터 r-th번째 동전까지 중 뒷면이 위로 향한 동전이 적어도 하나 있어야 한다는 뜻이다.

유일한 줄에 각 동전의 면을 선택하는 방법의 수를 109 + 7 = 1000000007로 나눈 나머지를 출력한다.

첫 번째 예제에서는 다음 방법들이 가능하다('O' — 앞면, 'R' — 뒷면):

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

두 번째 예제의 정보는 모순된다. 두 번째 동전은 앞면과 뒷면이 동시에 위를 향해야 하는데, 이는 불가능하다. 따라서 답은 0이다.