Description

粉兔由于看出题人不顺眼所以删除了背景。

对于一个 $n$ 个点，$\frac{n(n-1)}{2}$ 条有向边，边权均为 $1$ 的竞赛图「即对于任意两个不同的点，恰有一条有向边连接它们」，定义 $dis_{i,j}$ 为：从点 $i$ 走到点 $j$ 最短路径的长度。「特别地，如果不存在这样的路径，设它为 $\infty$。」

定义点 $i$ 的粉兔值 $R_i$ 为：$\max(dis_{i,j})$，$1 \leq j \leq n$。

定义一个竞赛图的巨佬值为：$\min(R_i)$，$1 \leq i \leq n$。

现在对于每一种不同的竞赛图，求他们巨佬值的和。结果请对 $19260817$ 取模。可以证明，不存在一个竞赛图的巨佬值为 $\infty$。

「两个竞赛图不同，当且仅当存在点 $i,j$，在其中一个图中有边 $i \to j$，而另一个图中有边 $j \to i$」

Input Format

输入到文件 ak.in 中。

一行一个正整数，$n$。

Output Format

输出到文件 ak.out 中。

一行一个整数，含义如题。

Sample

样例输入

3

样例输出

10

Hint

对于 $30\%$ 的数据，$n \leq 5$。
对于 $100\%$ 的数据，$2 \leq n \leq 10^9$。