콜라가 좋아

시간 제한1초메모리 제한1024 MB

요약
빨간 콜라 N개와 검은 콜라 M개를 모두 사용해 높이가 감소하지 않도록 콜라탑을 쌓되, 각 탑의 색 배치가 120도 회전에 대해 대칭인 경우의 수를 구한다.
난이도

어려움10점 중 8점

유형
조합론, 동적 계획법, 수학, 정수론
정답자
아직 제출이 없습니다

문제

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

유틸은 제로가 좋다. 그래서 유틸은 제로 콜라만 마신다.

동우와 유틸은 조개구이를 먹을 때면 콜라탑들을 쌓기 시작한다. 콜라탑은 삼각형의 모양이며, 높이 HH의 콜라탑은 11층에 콜라 HH개, 22층에 콜라 H−1H-1개, ⋯\cdots, HH층에 콜라 11개가 쌓여 있다. 그리고 각 콜라 캔을 원형으로 생각하고, 일반 콜라는 빨간색, 제로 콜라는 검정색을 칠해 도식화할 수 있다. 예를 들어 왼쪽 콜라탑을 도식화하여 오른쪽 그림으로 나타낼 수 있다.

동우가 친구 33명과 조개구이를 먹을 때 실제로 쌓은 높이 44의 콜라탑이다.

동우는 NN개의 일반 콜라를, 유틸은 MM개의 제로 콜라를 마셨다. 이제 이 N+MN+M개의 콜라 캔을 모두 사용하여 한 개 이상의 콜라탑을 쌓아, 탑의 높이가 감소하지 않는 순서로 나열하고자 한다. 이때, 각 콜라탑을 도식화한 그림에 대해, 각각을 시계 혹은 반시계 방향으로 120∘120^\circ씩 회전하더라도 원래와 모양이 같아야 한다.

이 조건을 만족하도록 N+MN+M개의 콜라 캔을 모두 사용하여 한 개 이상의 콜라탑을 쌓아 탑의 높이가 감소하지 않는 순서로 나열하는 경우의 수를 구해보자.

각 콜라탑의 높이는 최소 11이상이어야 하며, 탑을 나열한 순서가 다르면 다른 경우로 센다.

입력

첫 번째 줄에 정수 N,M(1≤N,M≤1,000)N,M(1\le N,M\le 1\\, 000)이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 정답을 998,244,353998\\, 244\\, 353로 나눈 나머지를 출력한다.

예제8

  1. 예제 1

    입력
    1 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    2 3
    
    예상 출력
    11
    
  3. 예제 3

    입력
    4 2
    
    예상 출력
    18
    
  4. 예제 4

    입력
    3 3
    
    예상 출력
    26
    
  5. 예제 5

    입력
    99 100
    
    예상 출력
    993099141
    
  6. 예제 6

    입력
    100 100
    
    예상 출력
    842726135
    
  7. 예제 7

    입력
    1000 999
    
    예상 출력
    398797344
    
  8. 예제 8

    입력
    1000 1000
    
    예상 출력
    855631817