Аллен выпустился из Муусского техмулогоческого института (MIT) и основал стартап! Аллен — президент стартапа. Он нанял \(n-1\) работника, у каждого из которых есть один непосредственный начальник. Если \(u\) является начальником \(v\), а \(v\) является начальником \(w\), то \(u\) является начальником \(w\). Кроме того, нет таких \(u\) и \(v\), что \(u\) является начальником \(v\) и \(v\) является начальником \(u\). У Аллена нет начальников. Аллен — сотрудник номер \(1\), все остальные пронумерованы от \(2\) до \(n\).
Наконец, Аллен должен назначить каждому в компании, включая себя, зарплату. Из-за бюджетных ограничений зарплата каждого из сотрудников должна быть между \(1\) и \(D\) включительно. Кроме того, никто не может получать больше, чем его начальник.
Помогите Аллену найти количество способов назначить сотрудникам зарплаты. Эта величина может быть достаточно большой, поэтому выведите ее по модулю \(10^9 + 7\).
Примечание
В первом примере сотрудники с номерами 2 и 3 подчиняются непосредственно Аллену. Три зарплаты по порядку могут быть \((1,1,1)\), \((2,1,1)\), \((2,1,2)\), \((2,2,1)\) или \((2,2,2)\).
Во втором примере сотрудник 2 подчиняется Аллену, а сотрудник 3 подчиняется сотруднику 2. Возможные зарплаты равны \((1,1,1)\), \((2,1,1)\), \((2,2,1)\), \((2,2,2)\), \((3,1,1)\), \((3,2,1)\), \((3,2,2)\), \((3,3,1)\), \((3,3,2)\), \((3,3,3)\).