% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
	\renewcommand{\tl}{$0.4$ сек.}
	\renewcommand{\ml}{$1024$ MB}
	\problem{Задача А2. ИЗБОРИ}
	\addauthor{Автор: Борис Михов}{2025}{12}{20}
	\renewcommand{\header}{
		XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
		Общински кръг, 20 декември 2025 г.\\
		Група A – 11, 12 клас
	}
	
	В Сашкаландия има $N$ граждани, номерирани с числата от $1$ до $N$, като всеки от тях може да гласува. В държавата има няколко партии, всяка от които има номер измежду числата от $1$ до $N$. Гражданинът с номер $i$ би гласувал единствено за партията с номер $P_i$.
	
	Сашка е изключително влиятелна фигура в Сашкаландия. Заради това всеки поданик на държавата се консултира с нея дали да гласува за предпочитаната от него партия или да пропусне изборите, като винаги следва съвета ѝ.  
	
	Така Сашка започнала да се питa следния въпрос -- по колко различни начина може да проведе консултациите, така че партията с най-много гласове да е спечелила мнозинството от народния вот?
		
	Формално: \textbf{колко непразни подредици\footnote{Непразна подредица на редица $P$ е непразна редица, получена чрез изтриване на няколко елемента от $P$ като се запазва реда на останалите.} на $P_1, P_2, \cdots, P_N$ имат мажорант\footnote{Елемент на редицата, който се среща стриктно повече пъти от половината от дължината на редицата.}?}
	
	Тъй като този брой може да бъде много голям, Сашка се интересува единствено от остатъка му по модул $10^9 + 7$. Като дясната ръка на Сашка, напишете програма \textbf{\texttt{elections}}, която го изчислява.
	
	\subsection{Бележка}
	Понеже $10^9+7$ е просто число, то от следствие на малката теорема на Ферма следва, че $x^{10^9+6} \equiv 1 \pmod {10^9+7}$ за всяко цяло $x$, неделящо се на $10^9+7$.
	
	Може да използвате следното приложение на този факт, а именно, че за всяко цяло число $x$, неделящо се на $10^9+7$, съществува \textbf{обратен елемент}, означен с $x^{-1}$, такъв че $x^{-1} \equiv x^{10^9+5} \pmod{10^9+7}$ и $x^{-1} \cdot x \equiv 1 \pmod{10^9+7}$. Казано неформално, може да се дели по модул $10^9+7$.
	
	\subsection{Вход}
	На един ред на стандартния вход е дадено цялото число $N$.  
	На втория ред са дадени $N$ числа, съответно $P_1, P_2, \cdots, P_N$.
	
	\subsection{Изход}
	На стандартния изход отпечатайте на един самотен ред отговора.
	
	\subsection{Ограничения}
	\begin{itemize}
		\item $1 \leq N \leq 2 \cdot 10^6$
		\item $1 \leq P_i \leq N$
	\end{itemize}
	\FloatBarrier
	\newpage
	
	\subsection{Подзадачи}
	\begin{table}[H]
		\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
			\hline
			\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $N$ & \textbf{Други ограничения}\\
			\hline
			$0$ & $0$ & $-$ & $-$ & Примерните тестове. \\ 
			\hline
			$1$ & $10$ & $0$ & $\leq 20$ & -- \\ 
			\hline
			$2$ & $15$ & $-$ & $\leq 10^5$ & $P_i \leq 2$ \\ 
			\hline
			$3$ & $15$ & $-$ & $\leq 10^5$ & Всяка партия има до двама гласоподавателя.\\ 
			\hline
			$4$ & $25$ & $0-1$ & $\leq 10^3$ & -- \\
			\hline
			$5$ & $25$ & $0-4$ & $\leq 10^5$ & -- \\
			\hline
			$6$ & $10$ & $0-5$ & $\leq 2 \cdot 10^6$ & -- \\
			\hline
		\end{tblr}
		\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
	\end{table}
	\FloatBarrier
	
	\subsection{Примери}
	\begin{table}[H]
		\begin{tblr}{|l|l|X[j]|}
			\hline
			\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
			\hline
			\texttt{\makecell[lt]{3\\2 1 2}} & 
			\texttt{5}
			& 
			{Изборите, изпълняващи условията, са от граждани със следните номера:\\
				\tabitem $\{1\}$\\
				\tabitem $\{2\}$\\
				\tabitem $\{3\}$\\
				\tabitem $\{1, 3\}$\\
				\tabitem $\{1, 2, 3\}$} \\
			\hline
			\texttt{\makecell[lt]{8\\1 3 4 3 3 2 3 1}} & 
			\texttt{104}
			& 
			{Едни примерни избори, следващи условието, биха били от гласуващи граждани с номера $\{1,2,3,4,5,6,7\}$, защото партия $3$ би имала $4$ гласоподавателя, което е повече от $\frac{7}{2}=3.5$. От друга страна, изборите, в които всички граждани гласуват, нямат мажорираща партия, защото всяка една от тях би имала до $\frac{8}{2}=4$ гласоподавателя.}\\ 
			\hline
		\end{tblr}
	\end{table}
	
\end{document}
