폭풍 속의 스크리머
시간 제한2초메모리 제한1024 MB
차원 D와 반지름 R이 주어질 때, 원점을 중심으로 한 구의 안이나 표면에 있는 모든 정수 점의 좌표 절댓값 합을 10^9+7로 나눈 나머지를 구합니다.
문제
내일 프로그래밍 학교의 다차원 데이터 보관실을 방문한 학생은 공기 조절이 되는 헬륨 보관함에 든 다차원 초구를 살펴볼 수 있다. 학생은 초구를 고르고 살펴보기 전에, 그 초구를 다룰 만큼 지식이 있음을 증명해야 한다. 초구는 차원과 정수 반지름이 제각각이며, 각각 별도의 잠금 보관함에 들어 있다. 차원과 반지름은 보관함 라벨에 적혀 있다. 보관함을 열려면 잠금장치에 특정 값을 입력해야 한다. 이 값은 초구의 차원과 반지름에 따라 정해진다. 초구의 중심을 원점에 둘 때, 내부 또는 표면 위에 있는 모든 정수 점에 대해 모든 좌표의 절댓값을 더한 합이 그 값이다. 합은 로 나눈 나머지로 입력한다.
차원 유클리드 공간의 정수 점은 개의 좌표가 모두 정수인 점이다.
보관실 관리자는 앞으로 초구를 더 들일 계획이다. 차원이 높은 초구는 손으로 계산하기 번거롭다.
보관함 속 초구에 맞는 잠금 값을 계산하는 프로그램을 작성하라.
입력
두 정수 와 이 주어진다 (, ). 는 보관함 속 초구의 차원이고, 은 반지름이다.
출력
주어진 초구가 든 보관함을 여는 값을 로 나눈 나머지로 출력한다.