Team Work

N명으로 이루어진 팀이 있다. 특정 작업을 위해 사람들로 이루어진 비어 있지 않은 임의의 부분집합을 선택할 수 있다. 작업에 x명이 참여할 때의 비용은 xk이다.

사람들로 이루어진 모든 비어 있지 않은 부분집합에 대한 비용의 합을 출력한다.

입력의 유일한 줄에는 전체 사람 수와 k (1 ≤ k ≤ 5000)을 나타내는 두 정수 N (1 ≤ N ≤ 109)이 주어진다.

모든 비어 있지 않은 부분집합에 대한 비용의 합을 109 + 7로 나눈 나머지를 출력한다.

첫 번째 예제에서는 비어 있지 않은 부분집합이 {1} 하나뿐이며, 그 비용은 11 = 1이다.

두 번째 예제에서는 비어 있지 않은 부분집합이 일곱 개 있다.

• {1}, 비용은 12 = 1

• {2}, 비용은 12 = 1

• {1, 2}, 비용은 22 = 4

• {3}, 비용은 12 = 1

• {1, 3}, 비용은 22 = 4

• {2, 3}, 비용은 22 = 4

• {1, 2, 3}, 비용은 32 = 9

총비용은 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24이다.