인접한 룩

오크 교수는 학생들을 위해 문제를 하나 준비하고 있다. 문제는 $n \times n$ 체스판에 $n$개의 룩을 서로 위협하지 않도록, 즉 어떤 두 룩도 같은 열이나 같은 행에 놓이지 않도록 배치하는 방법의 수를 세는 것이다.

그런데 이 문제는 너무 쉬워서, 오크 교수는 조건을 하나 더 붙이기로 했다. 두 룩이 대각선으로 인접해 있는, 즉 열도 이웃하고 행도 이웃한 룩 쌍이 정확히 $k$개인 배치의 수만 세고 싶다. 이 문제를 풀 수 있겠는가?

답은 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \leq t \leq 5000$).

각 테스트 케이스는 한 줄에 두 정수 $n$과 $k$로 주어진다 ($1 \leq n \leq 1000$; $0 \leq k \leq n-1$). $n$은 룩의 개수이고, $k$는 대각선으로 인접해야 하는 룩 쌍의 개수이다.

어떤 두 룩도 같은 행이나 같은 열에 있지 않으면서 대각선으로 인접한 룩 쌍이 정확히 $k$개가 되도록 $n$개의 룩을 놓는 방법의 수를 하나의 정수로 출력한다. 답은 $10^9 + 7$로 나눈 나머지로 나타내야 한다.