Dãy số

Hãy đếm xem có bao nhiêu dãy \(A = (A_1, A_2, \ldots, A_n)\) gồm \(n\) phần tử, mỗi phần tử là một số nguyên không âm không vượt quá \(k\), sao cho với mọi \(1 \le i < n\), tổng \(A_i + A_{i+1}\) là một số nguyên tố.

Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(10^9 + 7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\) (\(1 \le n \le 100\), \(1 \le k \le 1000\)).

Output

In ra số lượng dãy thỏa mãn modulo \(10^9 + 7\).

Scoring

• Có \(30\%\) số test ứng với \(1 \le n \le 5\), \(1 \le k \le 10\).

Notes

Với \(n = 2\), \(k = 2\), có \(5\) dãy thỏa mãn: \((0, 2), (1, 1), (1, 2), (2, 1), (2, 0)\).