在$n*n$的国际象棋中，放置若干个国王和$k$个车，使得国王之间不互相攻击，车之间不互相攻击，车不可攻击到国王（这并不代表国王不能攻击到车）。国王能攻击到它上下左右，左上左下右上右下八个位置的棋子，车可以攻击到同一行或同一列中的棋子，求方案总数对$1000000007$取模后的值。
第一行一个正整数$T$(大约10),表示数据的组数。 接下来每组数据的第一行包含两个正整数$n,k(1 \leq n \leq 15,0 \leq k \leq 15)$，表示棋盘的大小和车的数量
对于每组数据，输出1行，表示方案总数 mod $1000000007$
5 1 0 1 1 2 0 2 1 2 2
2 1 5 8 2