1248 : Mary 有棵有根树

Description

【题目背景】

Mary 有棵有根树，

有根树，有根树。

Mary 有棵有根树，

啊枝繁叶茂。

【题目描述】

出生于魔王家族的 Mary，从小便与同龄的普通人类有所不同。比如说，Mary 的头两侧长有一对犄角，可以捕捉到远处细微的变化；比如说，Mary 身上的魔力会吸引神秘的生物，这些友善的来客自在地游曳在魔王城中，将其点缀成了一座坐落于偏僻孤岛上的水族馆；再比如，Mary 有一棵与生俱来的有根树。

Mary 有棵有根树。

在 Mary 出生时，这棵有根树也一同降临在了世界上。照料好自己的有根树是魔王家族世世代代的传承，但让有根树生长的方法却因人而异。Mary 不知道如何让这棵只有一个结点的有根树生长，而她的父母也不得而知。虽然 Mary 的有根树从未生长，但是 Mary 像普通人类一样不断成长，她所能驾驭的魔力也随之越来越强。Mary 的成长获得了父母的认可，他们将魔王家族中象征着力量成熟的魔法——闪耀魔法传授给了 Mary。当 Mary 第一次成功施展了闪耀魔法时，她的有根树终于产生了变化：从原来的根结点上，长出了 $M$ 个新的结点。原来，每当 Mary 施展一次闪耀魔法时，她的有根树都会有一个叶结点恰好长出 $M$ 个可以区分的子结点。每次进行生长的叶结点是在所有尚未生长的叶结点中等概率随机产生的，而已经拥有 $M$ 个子结点的非叶结点不会再次生长。

Mary 想知道：在她总共使用了 $K$ 次闪耀魔法之后，她的有根树上各个结点的深度总和的期望。最初没有使用闪耀魔法时，只有一个结点的有根树的深度定义为 $0$。

Input

输入仅一行，包括两个由单个空格隔开的正整数 $M$，$K$，表示从一个结点上可以长出的子结点的数量，以及使用闪耀魔法的次数。保证 $1\le M\le 100$，$1\le K\le {10}^7$。

Output

输出一个数，表示 Mary 的有根树的结点深度和的期望。假设期望深度和化为最简分式后的形式为 $p/q$（即其中 $p,q$ 互质），请输出非负整数 $x$ 使得 $qx\equiv p(\mathrm{mod}1,000,000,009)$，且 $0\le x<1,000,000,009$。可以证明，在本题数据范围下，$x$ 存在且唯一。

Sample

6 2

18

2 6

600000038

83 613210

424200026

Hint

【样例解释 #0】

使用第一次闪耀魔法后，Mary 的有根树恰有 $1$ 个根结点和 $6$ 个叶结点。第二次使用闪耀魔法时，无论是哪一个叶结点进行生长，新长出的叶结点的深度均为 $2$。因此，结点深度和的期望为 $0\times 1+1\times 6+2\times 6=18$。

Source

Author

THU