Triples

Let m and n be two positive integers (5 ≤ m ≤ 100, 2 ≤ n ≤ 100). Consider the following sets of triples:

T_m, j = {(x, y, z) ∈ ℕ³ ⏐ x ≤ y ≤ z ≤ m and x^j + y^j = z^j},   j = 2, …, n,

where ℕ is the set of nonnegative integers (ℕ = {0, 1, 2, …}).

The problem asks you to compute the sum S_m,n:

where card(T_m, j) is the number of elements of the set T_m, j.

Input Specification

The input contains a single test case. The first line of the input contains the value of m, and the second line contains the value of n.

Output Specification

Output a single line with the value of the sum S_m,n.

Sample Input

1. 85
2. 95

download as text file

Output for Sample Input

1. 8128

download as text file

Original Problem

Southeastern Europe Regional Contest, 2014