26525번 - 빙고

문제

확률과 통계 수강생들이 빙고를 하고 있다. 이들의 빙고 게임은 다음과 같은 규칙으로 진행된다.

• 참가자들은 각자 $n \times n$ 정사각형 모양의 보드 위 각 칸에 1ドル$부터 $n^2$까지의 정수를 겹치지 않도록 하나씩 적어넣는다.
• 매 라운드에, 사회자는 1ドル$부터 $n^2$까지의 정수 중 하나를 부른다. 이때 이미 부른 수는 고르지 않는다.
• 참가자는 자신의 보드에서 사회자가 부른 수가 있는 위치를 찾아 색을 채운다.
• 사회자가 더 이상 수를 부르지 않기로 하면, 게임이 끝나고 점수가 계산된다. 각 참가자의 점수는 색을 채운 칸들로만 이루어진 줄의 수이다. 이때 고려하는 줄은 가로 $n$줄, 세로 $n$줄과 대각선 2ドル$줄로, 총 2ドルn+2$개의 줄이 있다.

위 빙고판의 점수는 5ドル$점이다.

사회자는 매우 공정하여, 매 차례에 부를 수 있는 수를 동일한 확률로 선택하여 부른다.

현재까지 진행된 게임의 상황을 반영한 참가자 $A$의 빙고판이 주어진다. 사회자가 정확히 $k$개의 수를 추가로 부를 예정이라고 할 때, $A$가 받을 최종 점수의 기댓값을 구해 보자.

입력

첫 번째 줄에 두 정수 $n,ドル $k$가 주어진다. $(1 \le n \le 100;$ 0ドル \le k \le n^2)$

두 번째 줄부터 $n$개의 줄에 걸쳐 빙고판의 상태가 0ドル$과 1ドル$로 이루어진 길이 $n$의 문자열로 주어진다. 0ドル$은 칸에 색이 채워지지 않았음을, 1ドル$은 색이 채워져 있음을 의미한다.

입력된 빙고판에는 채워지지 않은 칸이 적어도 $k$개 있음이 보장된다.

출력

$A$가 얻는 최종 점수의 기댓값을 $X$라고 할 때, 첫째 줄에 정수 $(n^2)! \times X$를 소수 10ドル^9+7$로 나눈 나머지를 출력한다.

주어진 입력의 범위에서 $(n^2)! \times X$가 정수가 된다는 사실을 증명할 수 있다.

제한

힌트