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