Разделение множества

У Руслана есть K друзей, и завтра у всех них день рождения. Вчера он купил N различных фотоальбомов и хочет подарить их своим друзьям. Конечно, каждому другу он должен подарить хотя бы один фотоальбом. Ваша задача — определить, сколькими способами это можно сделать.

Все фотоальбомы уникальны. Два распределения считаются одинаковыми, если они отличаются только порядком альбомов в подарках или людьми, получающими подарки.

Входные данные

В единственной строке входных данных указаны два числа, разделенные пробелом: 1 ≤ N ≤ 1000000000, 1 ≤ K ≤ min(N, 10).

Выходные данные

Выведите одно число — количество возможных способов распределения альбомов, взятое по модулю 2007.

Примеры