30787번 - 트리 안에 트리

문제

무방향 그래프인 높이 $t$의 포화 이진 트리 $T_t$는 1ドル$부터 2ドル^{t+1}-1$까지의 정점을 가지고, 1ドル$ 이상 2ドル^t-1$ 이하의 모든 정수 $i$에 대해 정점 $i$와 정점 2ドルi,ドル 정점 $i$와 정점 2ドルi+1$을 연결하는 간선이 있는 그래프이다.

두 그래프 $G,H$가 동형이라는 것은 $G$의 임의의 두 정점 $u,ドル $v$가 주어졌을 때 $u$와 $v$가 $G$에서 인접한 것과 $f(u)$와 $f(v)$가 $H$에서 인접한 것이 필요충분조건인 일대일 함수 $f:V(G)\rightarrow V(H)$가 존재한다는 것이다. 여기에서 $V(G)$와 $V(H)$는 각각 $G$와 $H$의 정점 집합을 의미한다.

$T_N$에서 0ドル$개 이상의 정점과 간선을 제거해서 $T_K$와 동형인 그래프를 만드는 방법의 가짓수를 구하자.

입력

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1\leq K\leq N\leq 5,円 000)$

출력

첫째 줄에 정답을 1ドル,円 000,円 000,円 007$로 나눈 나머지를 출력한다. 1ドル,円 000,円 000,円 007$은 소수이다.

제한

힌트