只剩下马了

题目描述

皇后、车、炮、国王……全被考完了，只能考一考马了

问一个$n*n$的棋盘里要放$k$只马，有多少种不同的方案？

马的规则参考国际象棋，能攻击到8个位置

如下图

$OXOXO\\ XOOOX\\ OOMOO\\ XOOOX\\ OXOXO$

M为马的位置，X是能攻击到的位置

输入格式

输入一行两个正整数 n，k。

输出格式

输出一行一个正整数，表示情况总数。答案保证在$2^{64}$范围内。

样例 #1

样例输入 #1

2 3

样例输出 #1

4

样例 #2

样例输入 #2

3 3

样例输出 #2

36

数据范围

第一到二个数据点$n=3$

第三到五个数据点$n=5$

第六到八个数据点$n=8$

第九到十个数据点$n=9$

对所有数据$k\le42$

数据加强：增加一组$n=10$的数据，尝试优化自己的算法吧