yqw的珂学难题（hard）
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

 本题与《yqw的数学难题（easy）》共享题目背景，只是n的范围不同，该版本可以视作困难版本。若能通过hard，则必能通过 easy。
珂朵莉给了 yqw 一个长度为 n的排列 p，排列中任一位置如果满足以下条件，则称该位置为 峰值：
位置 1：若 p[1] > p[2]，则 p[1] 为峰值。
位置 n：若 p[n] > p[n-1]，则 p[n] 为峰值。
位置 2 至 n-1：若 p[i] > p[i-1] 且 p[i] > p[i+1]，则 p[i] 为峰值。

珂朵莉定义了一个排列的价值为所有峰值位置的和，具体来说，对于排列 \{1,2,3\} ，位置3为峰值位置，而位置1和2不是，所以该排列的价值为 3 ，对于排列\{ 3,1,2\}，位置1和3为峰值位置，而位置2不是，所以该排列的价值为 1+3 = 4。

现在有一个长度为 n 的 随机排列，珂朵莉向 yqw 询问该随机排列价值的期望。
但是 yqw 的数学非常差，解决不了该问题，所以他想将这个问题交给你，你能帮他解决吗？

长度为 n 的排列是由 1 到 n 这 n 个整数，按任意顺序组成的数组，其中每个整数恰好出现一次。例如：\{2, 3, 1, 5, 4\} 是一个长度为 5 的排列。
而以下则不是有效的排列：\{1, 2, 2\}，因为存在重复元素。\{1, 3, 4\}，因为包含了超出范围的数。

输入描述:

输入一个正整数 n (2 ≤ n ≤ 10^{3}) ，代表随机排列的长度。

输出描述:

输出一个字符串，表示期望值的不可约分数（形如 A/B）。即使结果为整数，也需要输出成分数形式（例如，1  应输出为 1/1）。
示例1

输入

复制 
3

输出

复制 
8/3

说明

设每个排列的价值为V_i
对于 n=3，有以下6种情况：
\{1,2,3\}: 峰值位置为 3, \quad V_1 = 3;
\{1,3,2\}: 峰值位置为 2,\quad V_2 = 2;
\{2,1,3\}: 峰值位置为 1 和 3, \quad V_3 = 1+3 = 4;
\{2,3,1\}: 峰值位置为 2,\quad V_4 = 2;
\{3,1,2\}:峰值位置为 1 和 3,\quad V_5 = 1+3 = 4;
\{3,2,1\}: 峰值位置为 1,\quad V_6 = 1.
E = \frac{1}{6} \sum_{i=1}^{6} V_i = \frac{3+2+4+2+4+1}{6} = \frac{16}{6} = \frac{8}{3}.