牛牛的正方形
题号：NC21372
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛牛最近正在学二维几何，他碰到了下面这样一个问题
平面上有一些点，并且已知两个参数nlow, nhigh
牛牛用一个n*n(nlow <= n <= nhigh)的正方形去框，能框住多少不同的点集

输入描述:

第一行输入两个整数nlow, nhigh (1 ≤ nlow ≤ nhigh ≤ 108)
第二行输入一个整数m（1 ≤ m ≤ 40）,表示点的数量
接下来一行包含m个整数表示x坐标
接下来一行包含m个整数表示y坐标
坐标的范围[-1e8,1e8]

输出描述:

输出一个整数,对1e9+7取模
示例1

输入

复制 
5 5
3
-5 0 5
0 0 0

输出

复制 
5
示例2

输入

复制 
10 10
3
-5 0 5
0 0 0

输出

复制 
5
示例3

输入

复制 
1 100
3
-5 0 5
0 0 0

输出

复制 
6
示例4

输入

复制 
3 100000000
7
-1 -1 -1 0 1 1 1
-1 0 1 1 -1 0 1

输出

复制 
21
示例5

输入

复制 
64 108
11
-56 -234 12 324 -12 53 0 234 1 12 72
6 34 2 235 234 234 342 324 234 234 234

输出

复制 
26

备注:

子任务1：n <= 10
子任务2：n <= 20
子任务3：n <= 40