중첩된 충돌기 시스템

플랫랜드 정부는 하드론 충돌기를 짓는 것을 좋아한다. 그래서 중첩된 충돌기 시스템을 짓기로 했다.

각 충돌기는 중심이 정수 좌표에 있고 반지름이 양의 정수인 원이다. 충돌기 시스템은 하나 이상의 충돌기로 이루어진다. 가장 큰 충돌기를 제외한 각 충돌기는 바로 앞의 충돌기 안에 있어야 하지만, 그 충돌기와 점 하나를 공유할 수 있다.

충돌기를 지을 직사각형 부지가 있다. 부지에는 직교 좌표계가 표시되어 있고, 서로 마주 보는 두 꼭짓점의 좌표는 $(-n, -m)$과 $(n, m)$이다. 어떤 충돌기도 부지 밖으로 나가서는 안 되지만, 부지의 경계와 점을 공유할 수 있다.

플랫랜드 정부는 이런 시스템을 몇 가지 방법으로 지을 수 있는지 알고 싶어 했고, 그 계산을 당신에게 맡겼다. 이 수가 클 수 있으므로 $10^9$로 나눈 나머지를 구하면 된다.

두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 1000$).

중첩된 충돌기 시스템을 짓는 방법의 수를 $10^9$로 나눈 나머지를 출력한다.

두 번째 예에 대한 그림: