34171번 - 사이다가 좋아 서브태스크

동우는 제로가 싫다. 그래서 동우는 일반 사이다만 마신다.

유틸은 제로가 좋다. 그래서 유틸은 제로 사이다만 마신다.

민재는 스프라이트가 좋다. 그래서 민재는 스프라이트만 마신다.

편의상 일반 사이다, 제로 사이다, 스프라이트를 모두 사이다라고 하자.

그래서 동우와 유틸과 민재는 조개구이를 먹을 때면 사이다탑을 쌓기 시작한다. 사이다탑은 삼각형의 모양이며, 높이 $H$의 사이다탑은 $1$층에 사이다 $H$개, $2$층에 사이다 $H-1$개, $\cdots$, $H$층에 사이다 $1$개까지 쌓여 있다. 그리고 각 사이다 캔을 원형으로 생각하고, 일반 사이다는 초록색, 제로 사이다는 검은색, 스프라이트는 노란색을 칠해 도식화할 수 있다. 예를 들어 왼쪽 사이다탑을 도식화하여 오른쪽 그림으로 나타낼 수 있다.

이 문제를 위해 출제/검수진들이 마신 사이다탑이다. 밑변의 수직이등분선을 기준으로 대칭을 이룬다.

동우와 유틸과 민재는 총 $S=\frac{H\left( H+1 \right)}{2}$개의 사이다를 마셔 사이다탑을 만들고자 한다. 이때 이 사이다탑을 도식화한 그림에 대해, 세 변 중 최소 한 변의 수직이등분선에 대해 대칭이 되어야 한다. 이제 각자 몇 개의 사이다를 마실 지 정해야 한다. 동우는 $N$개의 일반 사이다를, 유틸은 $M$개의 제로 사이다를, 민재는 $K=S-N-M$개의 스프라이트를 마시고, 이 사이다 캔을 모두 사용해, 조건을 만족하는 높이 $H$의 사이다탑을 구성할 수 있는 경우의 수를 여러 상황에서 구하고 싶다. $S$가 정해져 있을 때, 주어진 $N,M,K$에 대해 조건에 맞는 사이다탑을 쌓을 수 있는 경우의 수를 구해보자.

첫 번째 줄에 양의 정수 $H(1\le H\le 50)$가 주어진다.

두 번째 줄에 쿼리의 개수 $Q(1\le Q\le\frac{1}{48}\left( H^4+2H^3+13H^2+12H+60 \right))$가 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 $N,M,K(0\le K\le M\le N$; $N+M+K=\frac{H\left( H+1 \right)}{2} )$가 공백으로 구분되어 주어진다.

$Q$개의 줄에 걸쳐 각 쿼리 별 정답을 $998\, 244\, 353$으로 나눈 나머지를 출력한다. 같은 쿼리는 여러 번 주어지지 않는다.