Məsələlər
Вася и последовательности
Вася и последовательности
Василий продолжает свои эксперименты с битовыми операциями. В этот раз он опять работает с операцией \textbf{XOR}. Сначала он случайным образом выбирает \textbf{N} натуральных чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_N}, после чего просит своего друга Виталия назвать единственное число \textbf{K}.
Плучив число K он пытается посчитать сколько существует таких последовательностей чисел \textbf{b_1}, \textbf{b_2}, ..., \textbf{b_N}, для которых выполняются сследующие условия:
\begin{enumerate}
\item \textbf{0} ≤ \textbf{b_i} ≤ \textbf{a_i}, для \textbf{1} ≤ \textbf{i} ≤ \textbf{N}.
\item \textbf{b_1}
\includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg}
\textbf{b_2}
\includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg}
...
\includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg}
\textbf{b_N} = \textbf{K}.
\end{enumerate}
Так как их количество может быть очень большим, он просит Вас помочь ему в этом. Чтобы Вам было проще он просит найти это количество по модулю \textbf{10^9+7}.
\InputFile
В первой строке задано число \textbf{N}, \textbf{1} ≤ \textbf{N} ≤ \textbf{100}. В стледующей строке задано \textbf{N} чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_N}, \textbf{1} ≤ \textbf{a_i} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{i} ≤ \textbf{N}. В третьей строке задано едиственное число \textbf{K}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10^9}.
\OutputFile
Выведите единственное число - количество последовательностей, которые удовлетворяют описанные выше условия, по модулю \textbf{10^9+7}.
Giriş verilənləri #1
5 1 2 3 4 5 5
Çıxış verilənləri #1
72