Screamers in the Storm

Time limit2sMemory limit1024 MB

Summary

Given dimension D and radius R, compute the sum of absolute coordinate values over all integer points inside or on a centered sphere, modulo 1000000007.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

Students visiting the Multidimensional Data Cabinet at Tomorrow Programming School may get access to multidimensional hyperspheres stored in air-conditioned helium cupboards. Before exploring a chosen sphere, a student has to prove they know enough to handle it. Spheres come in various dimensions and integer radii, each in a separate locked cupboard. The dimension and radius are written on the cupboard label. To unlock a cupboard, the student enters a specific value into its lock. The value depends on the dimension and radius of the sphere. It is the sum of the absolute values of all coordinates of all integer points that lie inside or on the surface of the sphere, when the center of the sphere is at the origin. The sum is entered modulo $10^9 + 7$ .

An integer point in a $d$ -dimensional Euclidean space is a point whose $d$ coordinates are all integers.

The cabinet manager plans to acquire more spheres. High-dimensional spheres can be tedious to work out by hand.

Write a program that calculates the value needed to unlock a cupboard with a sphere in the cabinet.

Input

The input contains two integers $D$ and $R$ ( $1 \le D \le 50$ , $1 \le R \le 50$ ), the dimension and the radius of the sphere inside a cupboard.

Output

Print the value that unlocks the cupboard with the given sphere, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
1 6
```
Expected output
```
42
```
Example 2
Input
```
3 5
```
Expected output
```
2850
```