格点谜题

考虑第一象限中的 A(x_a,y_a)、B(x_b,y_b)、C(x_c,y_c)、D(x_d,y_d) 格点（即坐标为整数 x,y；x>=0 且 y>=0）。

AB段与DC平行，AD与BC平行。

考虑 BC 段上的 N 个点 (M1, M2,..,MN)，将 BC 分成 N 个相等的段：
对于 x_c>x_b 和 y_c>y_b
M1(x_b+1*(x_c-x_b)/N, y_b+1*(y_c-y_b)/N),
M2(x_b+2*(x_c-x_b)/N, y_b+2*(y_c-y_b)/N),
..,
MN(x_b+N*(x_c-x_b)/N, y_b+N*(y_c-y_b)/N)=C(x_c,y_c)

M1、M2、..、MN 是 不一定是格点 但从 A 到 M1,M2,..,MN 绘制的所有线段在格点处与 BD 线段相交。

当 N=1000 时，ABCD 的最小面积是多少？

输入格式：面积(ABCD) Mod 10^9。