从前有一对好朋友，他们名叫小移和小换。他们都是远近闻名的排序大师！对于一个长度为 的排列 ，小移每次操作可以选一个区间将它循环右移一位，而小换每次操作可以交换两个不同元素的位置。
其中，排列 ，是指满足 的一个序列。
形式化地，
- 小移的每次操作为：选择一段区间 （），若原区间的元素为 ，则操作后这一区间的元素变为 ；
- 小换的每次操作为：选择两个不同的位置 （），交换 与 。
今天你打算主持一局黑影杀，结果平常总是参加的小移和小换却都没有来，你感觉很疑惑，于是你决定调查其中原委。原来是有个坏蛋来挑拨离间！这家伙先是对小移说：「你看 这个排列，你竟然要操作整整 次才能把它排序！要是小换来，一次就能排完，你实在是太不牛了，赶快退休吧！」小移愤怒地把他轰走了，可到了晚上这个排列却在小移心里挥之不去，他几乎一晚上没睡着……然后这个坏蛋又和小换讲：「你看 这个排列，你竟然要操作整整 次才能把它排序！换作小移来，一次就能完事，你实在是菜得没边了，速速退役吧！」小换愤怒地把他赶跑了，可到了晚上这个排列却在小换脑海里一直转悠，他简直做了一晚上噩梦……
这事简直是太魔怔了。当局者迷旁观者清，你打算用最直接的方式来彻底解除这个误会：对于给定的整数 ，你想对于任意的 计算出满足「当采用最小化操作次数的策略时，小移需要操作 次、小换需要操作 次来完成排序」的长度为 的排列数量 。让数据说话，他们就能充分认识彼此的能力，从而解开心结，成为更好的朋友。你能完成这个任务吗？当然由于排列数量可能很大，给定 ，请将答案对 取模。
请注意，对于两个长度为 的排列 和 ，被视为两个不同的排列，需要被统计两次，当且仅当存在 （）满足 。
请注意，上述文本中的排序，是指将排列从小到大排序。即将一个排列 ，通过操作变为 。
