Василий продолжает свои эксперименты с битовыми операциями. В этот раз он опять работает с операцией \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}.