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

\begin{document}

\renewcommand{\tl}{$0.1$ сек.}
\renewcommand{\ml}{$3$ MB}
\problem{Задача С23. МОДНИЦА}
\addauthor{Автор: Кинка Кирилова-Лупанова}{2026}{03}{16}
    \renewcommand{\header}{
    	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
    	Национален кръг\\
    	Варна, 13 – 16 март 2026 г.\\
    	Група C, 7 – 8 клас, Ден 2 \\
    }

\begin{wrapfigure}{r}{0.35\textwidth}
	\begin{adjustbox}{width=0.33\textwidth}
		\includegraphics{trendy.jpg}
	\end{adjustbox}
\end{wrapfigure}

Мария е голяма модница и почитателка на козметиката. В колекцията ѝ има стотици бурканчета с пудри, червила и кремове. Преди всяка разходка с Христо тя нанася грим, за да подчертае елегантността си.

Както е известно на всяка модница, не всички козметични средства се съчетават добре помежду си. За да подреди огромната си колекция, Мария наредила всички козметични продукти в един дълъг ред. На всяко бурканче $i$ тя съпоставила цяло число $a_i$ -- числова характеристика на нейния стил.

Мария измислила специално правило за оценка на съвместимостта на продуктите: за всяка група бурканчета тя изчислява така нареченото \textit{магическо число} -- най-големият общ делител (НОД) на техните числови характеристики. За един продукт магическото число е равно на самото това число: НОД($a_i$) = $a_i$.
 
Тъй като редицата от козметични продукти се оказала много дълга, за един грим Мария предпочита да използва само средствата, които стоят едно до друго, т.е. някаква  подредица от тази последователност. Предстоят много разходки с Христо и Мария иска всеки път да изглежда по различен начин.
	
Мария решила да разгледа \textbf{всички възможни} подредици (всички начини да избере последователни бурканчета), да изчисли магическото число за всяка от тях и след това да намери сумата на всички тези магически числа. 

Помогнете на Мария да намери това крайно число, като напишете програма \texttt{\textbf{trendy}}. 

Тъй като отговорът може да бъде много голям, изведете остатъка му при деление на $10^9+7$.

\subsection{Вход}
  От първия ред на стандартния вход се въвежда едно цяло число $n$ -- брой на козметичните продукти. 
  
 От втория ред на стандартния вход се въвеждат $n$ цели числа $a_1,a_2,…,a_n$ -- числовите характеристики на стила на продуктите.

\subsection{Изход}
На първия ред на стандартния изход програмата трябва да изведе едно цяло число -- сумата на \textit{магическите числа} на всички подредици, по модул $10^9+7$.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq n \leq 200 000$
	\item $1 \leq  a_i  \leq 10^9$
  \end{itemize}  

     \subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{$n$}\\
		\hline
		$1$ & $22$ & $\leq 250$ \\ 
		\hline
		$2$ & $15$ & $\leq 1000$ \\ 
		\hline
		$3$ & $22$ & $\leq 50 \; 000$ \\ 
		\hline
		$4$ & $41$ & $\leq 200 \; 000$ \\ 
		\hline
	\end{tblr}
	\caption*{Всеки тест се оценява \textbf{независимо}.}
\end{table}
  
\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{3\\
6 10 15
\\ }}
		& 
		\texttt{\makecell[lt]{39}}& 
		{Масив a = [6, 10, 15]. Нека намерим сумата на най-големите общи делители за всички подредици.\\
• Подредици с дължина 1:\\
– [6] → НОД = 6;\\
– [10] → НОД = 10;\\
– [15] → НОД = 15.\\
• Подредици с дължина 2:\\
– [6, 10] → НОД(6, 10) = 2;\\
– [10, 15] → НОД(10, 15) = 5.\\
• Подредици с дължина 3:\\
– [6, 10, 15] → НОД(6, 10, 15) = НОД(2, 15) = 1.\\
Обща сума:\\
6 + 10 + 15 + 2 + 5 + 1 = 39.
}\\
		\hline
       
		\texttt{\makecell[lt]{5\\
        12 4 8 6 1\\}}
		& 
		\texttt{\makecell[lt]{53 }}&{} \\
		\hline 
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
