Василько і послідовності

Василько продовжує свої експерименти із бітовими операціями. Цього разу він знову працює над операцією XOR. Спочатку він випадковим чином вибирає N натуральних чисел a_1, a_2, ..., a_N, після цього просить свого друга Віталія назвати єдине число K.

Отримавши число K він намагається порахувати скільки існує таких послідовностей чисел b_1, b_2, ..., b_N, для яких виконуються наступні умови:

1. 0 ≤ b_i ≤ a_i, для 1 ≤ i ≤ N.

2. b_1

   

   b_2

   

   ...

   

   b_N = K.

Оскільки їх кількість може бути дуже великою, він просить Вас допомогти йому у цьому. Щоб Вам було простіше він просить знайти цю кількість по модулю 10^9+7.

Вхідні дані

В першому рядку задано число N, 1 ≤ N ≤ 100. У наступному рядку задано N чисел a_1, a_2, ..., a_N, 1 ≤ a_i ≤ 10^9, 1 ≤ i ≤ N. У третьому рядку задано єдине число K, 1 ≤ K ≤ 10^9.

Вихідні дані

Виведіть єдине число - кількість шуканих послідовностей, які задовільняють описані вище умови, по модулю 10^9+7.

Приклади