题目描述

公元 2202 年，一种奇怪的传染病开始在一座拥有 $n$ 名市民的城市中传播。

为了阻止疾病扩散，专家发明了一种名为 Mysterious Oscar 的强效疫苗。在第 $0$ 天，有一名市民感染疾病，另有一名市民接种疫苗。

一名市民一旦接种疫苗，就会立刻痊愈，并且以后不会再感染或传播这种疾病。

在第 $d$ 天（$d>0$），按以下顺序发生两轮行动。

感染阶段

所有在第 $d$ 天之前已经感染的市民依次尝试感染其他人。

每名感染者会从当前所有“尚未感染且尚未接种疫苗”的市民中，等概率随机选择一人并将其感染。

如果轮到某名感染者行动时，已经不存在尚未感染且尚未接种疫苗的市民，那么这名感染者什么也不做。

接种阶段

感染阶段结束后，所有在第 $d$ 天之前已经接种疫苗的市民依次劝说其他人接种疫苗。

每名已接种者会从当前所有尚未接种疫苗的市民中，等概率随机选择两名不同的市民，并劝说他们接种疫苗。

如果轮到某名已接种者行动时，尚未接种疫苗的市民不足两人，那么他会劝说所有剩余的未接种者接种疫苗。

Grammy 想知道这种疾病会在多少天后彻底消失。请计算所有患者全部痊愈所需天数的期望值。

可以证明，答案能够写成最简分数

其中 $x,y$ 为整数，并且

你需要输出

也就是说，输出唯一的整数 $a$，满足

且

输入格式

输入仅一行，包含一个整数 $n$，表示城市人口数量。

输出格式

输出一个整数，表示所有患者全部痊愈所需天数的期望值对 $10^9+7$ 取模后的结果。

样例 1

输入：
2

输出：
1

样例 2

输入：
114

输出：
505208013

样例说明

在样例 1 中，第 $0$ 天有一名市民接种疫苗。第 $1$ 天，这名已接种者会劝说另一名市民，也就是唯一的患者接种疫苗，因此疾病一定会在第 $1$ 天彻底消失。