Системы вложенных коллайдеров

시간 제한2초메모리 제한1024 MB

요약
중심과 반지름이 정수인 원들을 서로 내접하거나 포함하도록 겹겹이 쌓되, 모두 직사각형 [-n,-m]에서 [n,m] 안에 들어가는 시스템의 수를 10^9로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 조합론, 수학, 기하
정답자
아직 제출이 없습니다

문제

Правительству страны Флатландия понравилось строить адронные коллайдеры. Поэтому было решено построить систему вложенных коллайдеров.

Каждый коллайдер --- это окружность с центром в точке с целыми координатами и целым положительным радиусом. Система вложенных коллайдеров состоит из одного или более таких коллайдеров. При этом, каждый коллайдер, кроме самого большого, должен находиться внутри предыдущего, но может иметь с ним одну общую точку.

Для постройки системы вложенных коллайдеров выделена прямоугольная площадка, размеченная прямоугольной системой координат так, что противоположные углы площадки имеют координаты (−n,−m)(-n, -m) и (n,m)(n, m). Конечно же, никакой коллайдер не должен выходить за пределы этой площадки, но может иметь с ее границей общие точки.

Правительству Флатландии стало интересно, сколькими способами они могут построить такую систему вложенных коллайдеров, и они поручили эту задачи вам. Так как это число может быть большим, достаточно посчитать его по модулю 10910^9.

입력

Во входном файле заданы два целых числа nn и mm (1≤n,m≤1000)(1 \le n, m \le 1000).

출력

В выходной файл выведите остаток от деления числа способов построить систему вложенных коллайдеров на 10910^9.

힌트

Иллюстрация ко второму примеру:

예제2

  1. 예제 1

    입력
    1 3
    예상 출력
    5

  2. 예제 2

    입력
    2 2
    예상 출력
    15