因版权问题,此题暂停评测,请等待重制数据后提交。
渐渐地,勇士和魔鬼发现,这种游戏可能要进行 回合,是根本不可能完成的。而在这期间,Lyra 凭借着超时代的排序能力早已完成了魔鬼所需的各项排序。于是魔鬼提议,勇士请魔鬼吃一顿饭,魔鬼便放他们走而用餐地点的决定权落到了 Lyra 手上。
作为首席排序使,Lyra 对数字有着超人类的敏感,她决定选择一家可以带来数学问题的餐馆。最终他们去了一家快餐店,这家快餐店有 种菜拍成一排,顾客依次走过 号菜,并选择其中的一些加入自己的盘子,最终需要付的钱就是选择的菜的数量。
有趣的是,这个餐馆只接受 种纸币,第 种面值为 ,且不设找零。此次前来营救 Lyra,勇士得到了滋滋国财政支持,他的钱可以认为是无限的(即每种面值的纸币都有无限个)。经过观察,Lyra 发现,魔鬼对食物并不挑剔,对于每种菜品,他都有 的概率把其加入盘子。
虽然勇士可以无限用钱,但是勇士不喜欢浪费,由于快餐店不设找零,付款的时候可能会有一血浪费掉的钱,即 种面值能组成的最少的大于等于饭钱的金额减去饭钱。Lyra 则更关心,浪费掉的金额的期望是多少。
显然这个期望乘以 一定是个整数,你只需要输出期望乘以 再对 取模后的结果。