#ACM0001. 自相残杀

自相残杀

自相残杀

题目背景

马上新年到了,小神龙正在走来......不好!前方被一大波恶龙占领了。

题目描述

已知小神龙有一个能力,它能够瞬间将所有恶龙传送到指定位置。

恶龙会无差别攻击近身的所有物体(上、左、下、右、左上、左下、右上、右下),并且恶龙只能攻击周围的 88 个格子,小神龙想要这些可恶的恶龙自相残杀。

可以想象小神龙的前方有一个 N×NN \times N 的棋盘,棋盘里有 KK 只恶龙(初始时恶龙互不攻击),请问小神龙怎样安排每个恶龙的位置,使得所有的恶龙都能相互攻击。

请输出使得所有的恶龙都能相互攻击到对方的方案数。

输入格式

一行两个正整数,表示棋盘大小和恶龙数量 N,KN,K

输出格式

一行一个正整数,表示方案数。

样例 #1

样例输入 #1

3 2

样例输出 #1

20

样例 #2

样例输入 #2

19 25

样例输出 #2

0

提示

对于 30%30\% 的数据:1N91 \le N \le 9

对于 100%100\% 的数据: 1N109,0KNN1 \le N \le 10^9, 0\le K \le N * N