-外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，JYY 已经联系好了黄金舰队，打算联合所有 JSOIer 抵御外星人的进攻。
在黄金舰队就位之前，JYY 打算事先了解外星人的进攻计划。现在，携带了监听设备的特工已经秘密潜入了外星人的母舰，准备对外星人的通信实施监听。
外星人的母舰可以看成是一棵 n 个节点、 n-1 条边的无向树，树上的节点用 1,2,\cdots,n 编号。JYY 的特工已经装备了隐形模块，可以在外星人母舰中不受限制地活动，可以神不知鬼不觉地在节点上安装监听设备。
如果在节点 u 上安装监听设备，则 JYY 能够监听与 u 直接相邻所有的节点的通信。换言之，如果在节点 u 安装监听设备，则对于树中每一条边 (u,v) ，节点 v 都会被监听。特别注意放置在节点 u 的监听设备并不监听 u 本身的通信，这是 JYY 特别为了防止外星人察觉部署的战术。
JYY 的特工一共携带了 k 个监听设备，现在 JYY 想知道，有多少种不同的放置监听设备的方法，能够使得母舰上所有节点的通信都被监听？为了避免浪费，每个节点至多只能安装一个监听设备，且监听设备必须被用完。