#8778. 「第四届小英雄杯」草莓老师的草莓蛋糕 普及+/提高

草莓老师买了 个不同风味的草莓蛋糕，准备给她的 个学生每人一个蛋糕。每个学生都有一个他最讨厌的蛋糕风味，但他对剩下的 种蛋糕风味都非常

喜欢。每位学生讨厌的蛋糕风味各不相同。草莓老师打算将这 个蛋糕分配给 个学生。每个学生都必须拿到一个他喜欢的蛋糕（即他不能拿到自己最讨厌的蛋

糕风味）。草莓老师希望你计算有多少种可能的分配方式，使得每个学生都拿到自己喜欢的蛋糕。分配方式可能很多，请将最后的结果对 取模。

输入一个整数 ，表示草莓老师购买了 个不同风味的草莓蛋糕。

输出一个整数，表示草莓老师有多少种不同的分配方式，使得每个学生都拿到一个他喜欢的蛋糕（即每个学生都不能拿到自己最讨厌的蛋糕）。

样例输入 1

复制4

样例输出 1

复制9

样例输入 2

复制3

样例输出 2

复制2