널빤지에서 널빤지로

자연과 접하고 도시의 소란에서 벗어나고 싶었던 바이타자르는 바이토밀 숲에서 벌목꾼이 되었다. 그의 현재 임무는 서쪽에서 동쪽으로 곧게 뻗은 줄에 자라는 특정 나무 $n$그루를 베는 것이다. 각 나무는 $m$개의 종 가운데 하나에 속하지만, 그는 일을 막 시작해서 실수도 하고 어떤 나무가 어떤 종인지 기억하지 못한다.

매일 그는 아직 베지 않은 나무 하나를 골라 그곳에서 동쪽으로 걸어가며, 지나치는 베지 않은 나무를 모두 벤다. 그날의 작업은 출발한 나무와 같은 종의 나무를 하나 벤 직후에 끝내야 한다. 그 나무가 그 종으로 처음 만난 나무일 필요는 없다. 잘린 통나무는 벤 순서대로 모아 싣고, 이렇게 실어야 짐이 보기 좋게 정돈된다. 또한 그는 매일 최소 두 그루를 베고 싶어 하는데, 일을 게을리하는 것처럼 보이지 않기 위해서다.

모든 나무를 항상 벨 수 있는 것은 아니다. 가능 여부는 각 나무가 어떤 종에 속하는지에 달려 있다. 며칠이 지난 뒤 바이타자르가 모든 나무를 벨 수 있는 나무 종의 순서열이 몇 개인지 구하라. 두 순서열은 어떤 나무가 한쪽에서 다른 종으로 적혀 있으면 서로 다른 것으로 본다. 답은 $10^9+7$로 나눈 나머지로 출력한다.

첫 번째이자 유일한 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 3000$, $1 \le m \le 10^9$). $n$은 베어야 할 나무의 수, $m$은 나무가 속할 수 있는 종의 수이다.

가능한 나무 종 순서열의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

예시 설명: 종을 1과 2로 나타내면, 바이타자르가 작업을 성공적으로 마칠 수 있는 나무 종 순서열은 다음과 같다.

• 1, 1, 1, 1
• 1, 1, 2, 1
• 1, 1, 2, 2
• 1, 2, 1, 1
• 1, 2, 2, 1
• 2, 1, 1, 2
• 2, 1, 2, 2
• 2, 2, 1, 1
• 2, 2, 1, 2
• 2, 2, 2, 2