R01428
연속 색칠 금지
골드 I레이팅
의견: 0
설명
길이 \(N\)인 칸들을 \(C\)가지 색으로 칠하려 한다. 다음 두 조건을 모두 만족하는 경우의 수를 \(10^9+7\)로 나눈 나머지를 구하여라.
- 이웃한 두 칸은 서로 다른 색으로 칠해야 한다.
- \(C\)가지 색을 모두 적어도 한 번씩 사용해야 한다.
제약
- \(1 \le C \le N \le 10^6\)
입력 형식
한 줄에 칸의 수 \(N\)과 색의 수 \(C\)가 공백으로 구분되어 주어진다.
출력 형식
조건을 만족하는 색칠 방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
예제 1
입력
3 2
출력
2
설명
칸 \(3\)개를 색 \(2\)가지로 인접 같은 색 없이, 두 색 모두 사용하는 방법: \(1{-}2{-}1\), \(2{-}1{-}2\)로 \(2\)가지이다. 포함 배제: \(2\cdot1^2 - 2\cdot0^2 = 2\).
예제 2
입력
4 3
출력
18
설명
경로 \(4\)칸에 색 \(3\)가지 모두 사용하며 인접 다른 색: 포함 배제로 \(3\cdot2^3 - 3\cdot2\cdot1^3 + 3\cdot1\cdot0^3 = 24 - 6 = 18\).
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
연속 색칠 금지
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
연속 색칠 금지
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기