小蓝在研究组合数学时，提出了“平衡位置”的概念。
对于 到 的一个排列 ，如果位置 满足以下条件，则称位置 是平衡位置：
其中，位置 左侧指位置 ，位置 右侧指位置 ，左侧、右侧均不包含位置 本身。
小蓝认为，如果一个排列中至少有 个平衡位置（ 表示向上取整），那么这个排列就被称为一个“好排列”。
现在，给定数字 ，请你计算 到 的所有排列中，好排列的数量。由于答案可能很大，请输出其对 取模后的结果。
输入一行，包含一个正整数 。
输出一行，一个整数，表示好排列数量对 取模后的结果。
4
7
当 时，一个好排列至少需要 个平衡位置。
以排列 为例：每个位置左侧都没有比当前位置元素更小的数，右侧也没有比当前位置元素更大的数，因此四个位置都是平衡位置。该排列是一个好排列。
长度为 的所有排列中，共有 个好排列，因此输出 。
对于 的评测用例，。
对于所有评测用例，。
