在 2202 年，一种奇怪的疾病开始在一个拥有 $n$ 个人的城市中传播。

为了防止疾病传播，专家们发明了一种强效疫苗，名为“神秘奥斯卡”（Mysterious Oscar）。在第 0 天，一名市民感染了疾病，另一名市民接种了疫苗。如果一个人接种了疫苗，他/她将立即痊愈，并且不会再感染或传播该疾病。

在随后的每一天 $d$ ($d > 0$)，感染者会逐一感染他人。每一位在第 $d$ 天之前就已经感染的市民都会等概率地选择一名未感染且未接种疫苗的市民进行感染。如果某时刻，一名感染者没有未感染且未接种疫苗的市民可供选择，那么他/她将什么都不做。

感染过程结束后，已接种疫苗的市民会逐一劝说他人接种疫苗。每一位在第 $d$ 天之前就已经接种疫苗的市民都会等概率地选择 2 名不同的未接种疫苗的市民，并劝说他们接种疫苗。如果某时刻，一名已接种疫苗的市民可选择的未接种疫苗的市民少于 2 名，那么他/她将劝说所有剩余的未接种疫苗的市民接种疫苗。

Grammy 想知道疾病完全消失需要经过多少天。请计算所有患者痊愈所需天数的期望值。

可以证明，答案可以表示为一个不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 为整数且 $y \not\equiv 0 \pmod{10^9 + 7}$。请输出该整数等于 $x \cdot y^{-1} \pmod{10^9 + 7}$ 的结果。换句话说，输出一个整数 $a$，满足 $0 \le a < 10^9 + 7$ 且 $a \cdot y \equiv x \pmod{10^9 + 7}$。

输入格式

仅一行，包含一个整数 $n$ ($2 \le n \le 1.4 \cdot 10^7$)，表示城市的人口。

输出格式

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

样例

样例输入 1

2

样例输出 1

1

样例输入 2

114

样例输出 2

505208013

说明

在第一个样例中，一名市民在第 0 天接种了疫苗，他/她在第 1 天劝说了另一名市民（唯一的患者）接种疫苗，因此疾病在第 1 天被完全治愈。