레이팅 미적용베시는 길이 \(N\) 단위의 캔버스 조각 (\(1 \leq N \leq 10^6\))을 손에 넣었고, 그것에 그림을 그리려 한다. 하지만 그림 붓을 구할 수가 없었다. 그 대신 서로 다른 색의 고무 도장 \(M\)개 (\(1 \leq M \leq 10^6\))가 있으며, 각 도장의 너비는 \(K\) 단위 (\(1 \leq K \leq 10^6\))이다. 눈앞에 펼쳐진 가능성에 놀란 베시는, 캔버스에 도장들을 어떤 순서로 찍어서 만들 수 있는 서로 다른 그림이 정확히 몇 가지인지 알고 싶어한다.
도장을 사용하려면 먼저 캔버스 위의 이웃한 정확히 \(K\)개의 단위 칸에 맞추어야 한다. 도장은 캔버스의 끝을 벗어날 수 없으며, 단위 칸의 일부만 덮을 수도 없다. 도장을 찍으면 덮인 \(K\)개의 단위 칸이 그 도장의 색으로 칠해진다. 각 도장은 여러 번 사용할 수도, 한 번만 사용할 수도, 아예 사용하지 않을 수도 있다. 하지만 베시가 작업을 마쳤을 때, 캔버스의 모든 단위 칸은 적어도 한 번은 칠해져 있어야 한다.
베시가 그릴 수 있는 서로 다른 그림의 수를 \(10^9 + 7\)로 나눈 나머지를 구해 베시를 도와주자. 겉보기에 똑같지만 서로 다른 도장 찍기 순서로 그려진 두 그림은 같은 그림으로 센다.
입력 케이스의 75% 이상에서 \(N,K \leq 10^3\)이다.
Problem credits: Dhruv Rohatgi
Problem credits: Dhruv Rohatgi
입력의 첫째 줄이자 유일한 줄에 세 정수 \(N\), \(M\), \(K\)가 주어진다. \(K \leq N\)이 보장된다.
가능한 그림의 수를 \(10^9 + 7\)로 나눈 나머지를 나타내는 정수 하나를 출력한다.
spainting.in · 출력을 쓸 파일 spainting.out3 2 26If the two stamps have colors A and B, the possible paintings are AAA, AAB, ABB,
BAA, BBA, and BBB.