　$N = 1110$ とおく．条件 1. より $f$ は全単射であるので，$I$ の部分集合 $A_1, A_2, ..., A_r$ であって以下を満たすものを得ることができる．
- どの $A_i$ についても，その元すべてを適当な順序で $a_1, a_2, ..., a_k$（$k$ は $A_i$ の元の個数）と並べれば，
$$f(a_1) = a_2，f(a_2) = a_3，...，f(a_{k-1}) = a_k，f(a_k) = a_1$$
が成り立つ．

- 任意の $I$ の元は，$A_1, A_2, ..., A_r$ の中のちょうど $1$ つに属する．

　以後， $f(n) \lt n$ なる $n \in I$ を**降下元**と呼ぶことにする．条件 2. よりどの $A_i$ も $3$ 個以上の元を含み，したがってどの $A_i$ も降下元を $1$ つ以上含む．また，ある同一の $A_i$ に含まれる $n$ をどのように選んでも $f^{k}(n) = n$ なる最小の $k$ は一定になるので，条件 3. より，どの $A_i$ もそれに含まれる降下元は最大元ただ $1$ つであることが分かる．さらには $r = 3$ が従い，$A_1, A_2, A_3$ の元の個数は相異なることも分かる．そこで $A_1, A_2, A_3$ の元の個数をそれぞれ $X, Y, Z\ (\geq 3)$ とおく．すると $X + Y + Z = N$ が成り立つ．\
　ここで正 $N$ 角形を与え，その頂点に対し周に沿って順に $1, 2, ..., N$ と整数を割り当てよう．すべての $n \in I$ について頂点 $n$ と頂点 $f(n)$ を線分で結ぶ操作を行い，$N$ 本の線分を与えると，これらの線分は $X$ 角形，$Y$ 角形，$Z$ 角形をそれぞれ $1$ つずつ描くことが分かる．なお，これら $3$ つの多角形はいずれも自己交差をもたない（どの $A_i$ も降下元を $1$ つしかもたないからである）．\
　ここで得た多角形 $3$ つを $B_1, B_2, B_3$ と表す．多角形 $B_i$ に対し，最大・最小の整数が割り当てられた頂点同士結ぶ辺を除いて得られる折れ線を $\tilde{B}_i$ と表すと，条件 4. は「$\tilde{B}_1, \tilde{B}_2, \tilde{B}_3$ のうちどの $2$ つも互いに交わらない」と同値であるが，以下に与える補題によりこれは「$B_1, B_2, B_3$ のうちどの $2$ つも互いに交わらない」とも同値であることが分かる．

---
**補題.**　ある円に $2$ つの多角形 $P_1, P_2$ が内接しており，これらは頂点を互いに共有しないものとする．このとき，$P_1$ と $P_2$ が交わりをもつならば，$P_1, P_2$ からそれぞれ辺を $1$ つずつ除いて得られる折れ線 $\tilde{P}_1, \tilde{P}_2$ も交わりをもつ（これは取り除く辺の選び方に依らず成り立つ）．

<details><summary>補題の証明<\/summary>
　まずは $P_2$ の頂点によって円周をいくつかの円弧に分けることを考える．$P_1, P_2$ が交わりをもつという仮定から，$P_1$ の辺のうち少なくとも $2$ 本は異なる円弧同士をつなぐ．その $2$ 本のうち少なくとも一方は $\tilde{P}_1$ に含まれるのでそれを $l_1$ とおく．$l_1$ は $P_2$ のうち $2$ 辺と交わりをもち，その $2$ 辺のうち少なくとも一方は $\tilde{P}_2$ に含まれるのでそれを $l_2$ とおく．$l_1, l_2$ の交点が，$\tilde{P}_1, \tilde{P}_2$ の交点の $1$ つである．
<\/details>

---

　ここまでの議論から，$3 \leq X \lt Y \lt Z$ かつ $X + Y + Z = N$ を満たす整数の組 $(X, Y, Z)$ すべてに対する以下の要領による $X$ 角形，$Y$ 角形，$Z$ 角形の配置方法の個数の総和が，今回求めるべき個数に等しいことが分かる．
- $3$ つの多角形の頂点は，すべてある $1$ つの正 $N$ 角形の頂点と重なる．
- $3$ つの多角形はいずれも自己交差をもたない．
- $3$ つの多角形のうちどの $2$ つも互いに共有点をもたない．

そこで $(X, Y, Z)$ を $1$ つ固定し，配置方法の個数を求めよう．以下 $2$ つのケースが挙げられる．

**Case 1.**　ある $1$ つの多角形が周上に正 $N$ 角形の対角線を $2$ 本含み，残り $2$ つは周上に対角線を $1$ 本しか含まない場合．\
**Case 2.**　$3$ つの多角形すべてが，周上に正 $N$ 角形の対角線を $1$ 本しか含まない場合．

　Case 1. は，例えば $X$ 角形が対角線を $2$ 本含むときは，最初に $Y$ 角形，$Z$ 角形をこの順で配置する方法を考える．$Y$ 角形の配置は $N$ 個の頂点のうち隣接する $Y$ 個を選ぶ方法を考えればよく，それは $N$ 通りある．$Z$ 角形の配置は $N - Y = X + Z$ 個の頂点から両端 $2$ つを除いた $X + Z - 2$ 個のうち，隣接する $Z$ 個を選ぶ方法を考えればよく，それは $X - 1$ 通りある．よって $N(X-1)$ 通り数えられる．対角線を $2$ 本含む多角形が $Y$ 角形，$Z$ 角形の場合も同様に，それぞれ $N(Y-1), N(Z-1)$ 通りずつ数えられるので，このケースでは全部で $N(X + Y + Z - 3)= N^2 - 3N$ 通りの配置が得られる．\
　Case 2. は正 $N$ 角形から隣接する $X, Y, Z$ 個の頂点を選ぶ方法を考えればよく．円順列の考え方からこれは $N \times (3 - 1)! = 2N$ 通りである．\
　よって，$2$ ケース合わせて $N^2 - N$ 通りの配置が得られる．この配置数は $(X, Y, Z)$ の選び方に依らないことに注意せよ．

　次に $3 \leq X \lt Y \lt Z$ かつ $X + Y + Z = N$ なる整数の組 $(X, Y, Z)$ の個数 $M$ を求めよう．以下のように $3$ つの非負整数 $x, y, z$ を与える．
$$x = X - 3，y = Y - X - 1，z = Z - Y - 1$$
するとこの $x, y, z$ は
$$3x + 2y + z = 1098$$
を満たすので，整数の組 $(x, y)$ であって
$$x \geq 0，y \geq 0，3x + 2y \leq 1098$$
を満たすものの個数を調べればよく，これは $xy$ 平面上の $3$ 点 $(0, 0), (366, 0), (0, 549)$ を頂点とする直角三角形の周および内部にある格子点の個数に等しい．周上に $1098$ 個あることに注意しPickの定理を適用すると
$$(M - 1098) + \frac{1098}{2} - 1 = \frac{366 \times 549}{2}$$
が得られ，これを解くことで $M = 101017$ が得られる．

　以上より，求める個数は
$$M(N^2 - N) = \mathbf{124350916830}$$
である．
公式解説
https://onlinemathcontest.com/contests/omce008/editorial/7956
多少腕力を使います.

---

 公式解説の $3x+2y+z=1098$ を満たす非負整数 $(x,y,z)$ の数え上げについて, これは以下の冪級数の $x^{1098}$ の係数となります.
$$
\begin{aligned}
&(1+x^3+x^6+…)(1+x^2+x^4+…)(1+x+x^2+…)\\\\
&=\frac{1}{1-x^3}\frac{1}{1-x^2}\frac{1}{1-x}\\\\
&=\frac{1+x^3}{1-x^6} \frac{1+x^2+x^4}{1-x^6} \frac{1+x+x^2+x^3+x^4+x^5}{1-x^6}\\\\
&=\frac{1+\cdots+4x^6+\cdots+x^{12}}{(1-x^6)^3}
\end{aligned}
$$
$1098=6\times 183$ であるので,
$$M=\binom{183+2}{2}+4\binom{182+2}{2}+\binom{181+2}{2}=101017$$
と求めることができます.

---

　$3x,2y,z$ の $6$ で割った余りを先に決め打ちしてるとも考えられます.
公式解説のMの求め方の別方針
https://onlinemathcontest.com/contests/omce008/editorial/7956/661
　$1$ 以上 $1110$ 以下の整数全体からなる集合を $I$ と表します．関数 $f \colon I \to I$ であって以下 $4$ つの条件をすべてみたすものは全部でいくつありますか？

- **条件 1.**　$f(1), f(2), ..., f(1110)$ はどの $2$ つも相異なる．
- **条件 2.**　$f^{2}(n) = n$ なる $n \in I$ は存在しない．
- **条件 3.**　$f(n) \lt n$ なる $n \in I$ がちょうど $3$ 個存在する．さらに，それらを $n_1, n_2, n_3$ としたとき，各 $i \in \\{1, 2, 3\\}$ に対し $f^{k}(n_i) = n_i$ なる最小の正整数 $k$ を $k_i$ と定めると，$k_1, k_2, k_3$ はどの $2$ つも相異なる．
- **条件 4.**　どのような $m, n \in I$ に対しても $m \lt n \lt f(m) \lt f(n)$ は成り立たない．

　ここで，任意の正整数 $k$ について，関数 $f^{k} \colon I \to I$ は以下のように定義されます．
- 任意の $n \in I$ について，$f^{1}(n) = f(n)$ である．
- 任意の $n \in I$ と任意の正整数 $k$ について，$f^{k+1}(n) = f(f^{k}(n))$ である．