2007 AIME II Problem 8

A rectangular piece of paper measures 4 units by 5 units. Several lines are drawn parallel to the edges of the paper. A rectangle determined by the intersections of some of these lines is called *basic* if

(i) all four sides of the rectangle are segments of drawn line segments, and (ii) no segments of drawn lines lie inside the rectangle. Given that the total length of all lines drawn is exactly 2007 units, let N be the maximum possible number of basic rectangles determined. Find the remainder when N is divided by 1000.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.