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

\begin{document}

\renewcommand{\tl}{$0.4$ сек.}
\renewcommand{\ml}{$5$ MB}
\problem{Задача GT21. БИТОВА МАГИЯ}
\addauthor{Автор: Кинка Кирилова-Лупанова}{2026}{05}{07}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 5 май 2026 г.\\
	Група G
}

\begin{wrapfigure}{r}{0.30\textwidth}
	\begin{adjustbox}{width=0.30\textwidth}
		\includegraphics{magic.jpg}
	\end{adjustbox}
\end{wrapfigure}
В древна школа по магии магьосниците работят със специални \textit{магически кодове.}
Всеки магически код се представя като шестнадесетично число. Например магическият код 1F означава \(1 \cdot 16 + 15 = 31\).

Всеки магьосник иска да създаде магически код $x$, който да съдържа всички магически свойства на базовия код $b$. За да проверят това, магьосниците използват древната операция побитово И ($\&$) върху двоичното представяне на числата:
 
 \vspace{0.1em}
\begin{itemize}
	\item ако в даден бит и $x$, и $b$ имат 1, резултатът е 1; 
	\item в противен случай   резултатът е 0. 
  \end{itemize} 

Магическият код $x$ е достатъчно силен, ако: $ x \& b = b$.  Това означава, че всички единични битове на $b$ присъстват и в $x$.

Дадени са три шестнадесетични числа: $l$ — най-слабият допустим магически код, 
$r$ — най-силният допустим магически код, $b$ — базовият магически код.

Напишете програма \texttt{\textbf{magic}}, която намира колко различни магически кода $x$ съществуват, такива че $l ≤ x ≤ r$ и  изпълняват условието $ x \& b = b $.  

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

\subsection{Вход}
     От първия ред на стандартния вход се въвежда едно цяло число $l$. 
     
  От втория ред на стандартния вход се въвежда едно цяло число $r$. 
  
  От третия ред на стандартния вход се въвежда едно цяло число $b$. 
  
  Всяко число е зададено в шестнадесетична бройна система без водещи нули (освен случая на числото 0) и се състои от символите $0$ – $9$ и $ A – F$. 

 \subsection{Изход}
На първия ред на стандартния изход програмата трябва да изведе едно цяло число – броя на валидните магически кодове $x$, които удовлетворяват условията на задачата. 

Отговорът да се изведе в десетична бройна система без водещи нули по модул $10^9+7$.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq $ брой символи на всеки ред $ \leq 50 000$
	\item $0 \leq  l  \leq r$
	\item $0 \leq l, r, b \leq 16^{50 000} $
  \end{itemize}  
  
  \subsection{Подзадачи}
  
  \begin{center}
% \renewcommand{\arraystretch}{1.3}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & 
\textbf{Точки} & 
\parbox{3cm}{\textbf{\centering\\Необходими\\подзадачи\\\vspace{2mm}}} &
\parbox{6cm}{\textbf{\centering\\Допълнителни\\ограничения\\\vspace{2mm}}}
\\ \hline
0  & 0  &      & Примерите от условието.            \\ \hline
1  & 10 &      & $0 \le r, b < 16^4$, $l = 0$       \\ \hline
2  & 5  & 1    & $0 \le l, r, b < 16^4$             \\ \hline
3  & 10 & 1    & $0 \le  r, b < 16^7$, $l = 0$      \\ \hline
4  & 6  & 1--3 & $0 \le l, r, b < 16^7$             \\ \hline
5  & 10 & 1, 3 & $0 \le  r, b < 16^{15}$, $l = 0$   \\ \hline
6  & 7  & 1--5 & $0 \le l, r, b < 16^{15}$          \\ \hline
7  & 14 & 1,3,5& $0 \le r, b < 16^{1000}$, $l = 0$  \\ \hline
8  & 7  & 1--7 & $0 \le l, r, b < 16^{1000}$         \\ \hline
9  & 11 &1,3,5,7& $0 \le r, b < 16^{50\,000}$, $l = 0$ \\ \hline
10 & 12 &      & $0 \le l, r < 16^{50\,000}$, $b = 0$    \\ \hline
11 & 8  & 1--10& $0 \le l, r, b < 16^{50\,000}$         \\ \hline
\end{tblr}
\caption*{Точките за дадена подзадача се получават само ако всички тестове, предвидени за нея и необходимите подзадачи са успешно преминати.}
\end{table}
\end{center}


\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{8\\
F\\5}}
		& 
		\texttt{\makecell[lt]{2}}& 
		{Подходящите стойности на $x$ са шестнадесетичните числа D и F.
}\\
		\hline
       
		\texttt{\makecell[lt]{2\\
F9\\
A\\}}
		& 
		\texttt{\makecell[lt]{60 }}&{} \\
		\hline 
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
