Lemon Chandelier

<div>Damyoo is an artisan who has been making chandeliers for $49$ years. His chandeliers are completed by hanging $N$ lemons of various colors on a circular frame. The number of available colors is $N$, and multiple lemons of the same color can be used. There are sufficiently many lemons of each color. Through long experience, he realized that a chandelier is <span style="font-weight: bold;">beautiful</span> if and only if it satisfies the following condition:</div><blockquote>For any four distinct lemons $P, Q, R, S$, if the colors of $P$ and $Q$ are the same, the colors of $R$ and $S$ are the same, and the colors of $P$ and $R$ are different, then the segment $PQ$ and $RS$ must not intersect.</blockquote><div>Find the number of <span style="font-weight: bold;">beautiful chandeliers</span> among all possible $N^N$ chandeliers. <span style="font-weight: bold;">However, even if two chandeliers look the same when rotated, they are treated as different chandeliers.</span></div>

<div>The input is given in the following format.<blockquote style="margin: 0px; border-left: 4px solid rgba(99, 102, 241, 0.35); background: none 0% 0% / auto repeat scroll padding-box border-box rgba(99, 102, 241, 0.05);">$N$</blockquote></div>

<ul style="margin: 0px 0px 14px;"><li>$3 \leq N \leq 1 \ 000 \ 000$.</li></ul>