어떤 프로그래밍 콘테스트에서는 경기 뒤 친목 모임에서 빙고 게임을 하는 관습이 있다. 다만 이 게임에서 쓰는 빙고 카드는 조금 특별해서, 아래 조건을 따라 만든다.

• 빙고 카드는 \(N\)행 \(N\)열 칸으로 나뉘고, 각 칸에는 양의 정수가 하나씩 적혀 있다. 그 정수들은 모두 서로 다르다.
• 칸에 적힌 정수는 \(1\) 이상 \(M\) 이하이다.
• 카드에 적힌 \(N \times N\)개 정수의 합은 \(S\)이다.
• 어느 열을 보아도, 위에서 아래로 정수는 오름차순이다.
• 어느 칸의 정수든, 그 칸보다 왼쪽 열의 어떤 정수보다도 크다.

위 조건을 만족하는 빙고 카드를 되도록 많이 만들고 싶다. 같은 카드는 두 장 이상 만들지 않는다. 만들 수 있는 빙고 카드 장수의 최댓값을 \(100000\)으로 나눈 나머지를 출력하는 프로그램을 작성하라.