用最少的 $6^k,9^k$ 表示 $n$。$(1\le n\le 10^{12})$
预处理 $n\lt 10^6$ 的答案，然后启发式搜索。
求不存在某个长度超过 $m$ 的连续子串恰好是 $i,i+1,i+2\cdots i+k-1$ 或 $i+k-1,i+k-2\cdots i$ 的 $1\sim n$ 的排列的个数。
数据保证 $m\ge \lfloor \frac n2\rfloor$。
称 $i,i+1,i+2\cdots i+k-1$ 或 $i+k-1,i+k-2\cdots i$ 为长度等于 $k$ 的非法子串。
显然，当 $m\ge \lfloor \frac n2\rfloor$ 时任意一个排列不存在两个不相交的长度超过 $m$ 的非法子串。
设 $f(n,m)$ 表示所有 $1\sim n$ 的排列包含的长度为 $m$ 的非法子串个数。
考虑非法子串的元素选中，共 $n-m+1$ 种，然后将非法子串当成一个元素和其他正常元素可以任意排列，因此有 $(n-m+1)$ 排列方式。
最后 $m$ 超过 $1$ 时还要考虑 $i,i+1,i+2\cdots i+k-1$ 或 $i+k-1,i+k-2\cdots i$ 不同的贡献，于是有
$$ f(n,m)=(n-m+1)(n-m+1)!(1+(m\neq 1)) $$
最后，考虑每个含有长度超过 $m$ 的非法子串的排列，假设他含有的最长非法子串长度为 $k$，则他对 $f(n,m+1)$ 的计数贡献为 $k-m$。
同时他对 $f(n,m+2)$ 的计数贡献为 $k-m-1$。于是每个含有长度超过 $m$ 的非法子串的排列对 $f(n,m+1)-f(n,m+2)$ 的贡献恰好为 $1$。
于是 $f(n,m+1)-f(n,m+2)$ 就等于所有含有长度超过 $m$ 的非法子串的排列个数。根据容斥，答案为 $n!-f(n,m+1)+f(n,m+2)$。
$$ \sum_{i_1=0}^n\sum_{i_2=0}^n\cdots \sum_{i_k=0}^n\sum_{d=1}^g[d\ast(i_1+i_2+\cdots i_k)\le n]\prod_{j=1}^k{n-d\ast \sum_{h=1}^{j-1}i_h\choose d\ast i_j} $$
$1\le g,k\le 3,n\le 10^9$
化简，得上式等于
$$ \sum_{d=1}^g\sum_{i_1+i_2+\cdots +i_k\le n}[d\mid i_1,d\mid i_2\cdots d\mid i_k]\frac {n!}{(i_1)!(i_2)!\cdots (i_k)!(n-i_1-i_2-\cdots i_k)!} $$
由于 $g$ 很小，可以暴力枚举 $d$，对固定的 $d$，相当于查询长度为 $n$ 的 $k+1$ 重集排列的个数，满足前 $k$ 种元素出现次数都是 $d$ 的倍数。
设 $\text{dp}(n,i_1,i_2\cdots i_k)$ 表示长度为 $n$ 的 $k+1$ 重集排列的个数，满足前 $k$ 种元素出现次数模 $d$ 分别为 $i_1,i_2\cdots i_k$。
用 $k$ 位 $d$ 进制数表示状态 $(i_1,i_2\cdots i_k)$，矩阵快速幂加速 $\text{dp}$，时间复杂度 $O\left(g^{3k}\log n\right)$。