아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

클리커

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

요약
n의 모든 정수 분할 각각에 1부터 m까지의 등급을 부여하는 경우의 수를 10^9-401로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

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

문제

무방향 그래프의 모든 연결 요소가 클리크(완전 그래프)이면, 이 그래프를 클리커라고 부른다. 두 클리커는 서로 동형이면(정점의 이름만 바꾸어 같아지면) 같은 것으로 본다. 따라서 정점이 nn개인 클리커는 각 연결 요소의 크기를 모은 다중집합으로 완전히 결정된다.

Maurycy는 정점이 nn개인 서로 다른 클리커를 모두 그린 뒤, 각 클리커의 아름다움을 {1,2,…,m}\{1, 2, \dots, m\} 중 한 정수로 평가하려고 한다(서로 다른 클리커가 같은 점수를 받아도 된다). 점수를 매기는 방법은 모두 몇 가지인가? 답이 매우 클 수 있으므로 109−40110^9 - 401로 나눈 나머지를 출력한다.

아래 그림은 n=3n = 3일 때의 모든 클리커를 보여 준다.

n = 3인 모든 클리커

입력

한 줄에 두 정수 nn과 mm이 공백 하나로 구분되어 주어진다 (1≤n,m≤2000001 \le n, m \le 200000). 각각 클리커의 정점 수와 사용할 수 있는 점수의 개수를 뜻한다.

출력

점수를 매기는 방법의 수를 109−40110^9 - 401로 나눈 나머지를 한 정수로 출력한다.

예제1

  1. 예제 1

    입력
    3 2
    
    예상 출력
    8