Vasılko və ardıcıllıqlar
Vasylko bit əməliyyatları ilə təcrübələrini davam etdirir. Bu dəfə o, XOR əməliyyatı üzərində işləyir. Əvvəlcə təsadüfi olaraq N təbii ədədləri a_1, a_2, ..., a_N seçir və sonra dostu Vitaliydən bir ədəd K söyləməsini xahiş edir.
K ədədini aldıqdan sonra Vasylko, aşağıdakı şərtləri ödəyən neçə ardıcıllığın b_1, b_2, ..., b_N mövcud olduğunu hesablamağa çalışır:
Hər bir i üçün, 0 ≤ b_i ≤ a_i, burada 1 ≤ i ≤ N.
b_1 XOR b_2 XOR ... XOR b_N = K.
Çünki bu ardıcıllıqların sayı çox böyük ola bilər, Vasylko sizdən bu işdə ona kömək etməyinizi xahiş edir. O, bu sayını 10^9+7 modulu ilə tapmağınızı istəyir.
Giriş verilənləri
Birinci sətirdə N ədədi verilir, burada 1 ≤ N ≤ 100. İkinci sətirdə N ədədləri a_1, a_2, ..., a_N, burada 1 ≤ a_i ≤ 10^9, 1 ≤ i ≤ N verilir. Üçüncü sətirdə isə tək bir ədəd K, 1 ≤ K ≤ 10^9 verilir.
Çıxış verilənləri
Təsvir edilən şərtlərə uyğun olan ardıcıllıqların sayını 10^9+7 modulu ilə çıxarın.