Easy Power

Phuong là một lập trình viên yêu nghề, ngoài ra cô ấy còn rất đam mê với toán học. Cô ấy rất thích những phép tính liên quan đến số mũ.Một ngày đẹp trời cô ấy quyết định phát minh ra trò chơi của riêng mình.Trò chơi được mô tả như sau:

Phuong có n ô vuông được xếp theo hàng ngang từ trái sang phải.Ban đầu tất cả các ô vuông đều khác rỗng.Phuong đã đánh dấu n ô vuông trái sang phải bằng mảng arr chứa các con số 2 và 4.Cô ấy bắt đầu trò chơi như sau:Tất cả các ô vuông di chuyển sang bên phải của chúng, theo quy tắc sau đây:

• B1:  Duyệt các ô vuông từ trái sang phải( chúng khác rỗng )
• B2: Ô vuông hiện tại sẽ dừng lại nếu đó là ô cuối cùng của hàng( ô bên phải nhất) hoặc ô bên phải gần nhất mà khác rỗng của ô đó có giá trị khác ô hiện tại( ví dụ ô hiện tại là i và j là ô phải gần nhất của ô thứ i mà khác rỗng và arri != arrj ) chúng ta sẽ chuyển sang ô bên tiếp theo.
         
        Ô vuông hiện tại không phải là ô cuối cùng và ô bên phải gần nhất mà khác rỗng của ô đó có giá trị bằng ô hiện tại( ví dụ ô hiện tại là i và j là ô phải gần nhất của ô thứ i mà khác rỗng và arri = arrj), ô vuông thứ j sẽ được cộng thêm giá trị của ô vuông i và ô vuông thứ i trở nên rỗng. Sau đó tiếp tục duyệt lại B1.

Sau khi tất cả ô vuông đã di chuyển xong, dãy số đó được coi là tuyệt vời nếu chúng tồn tại ít nhất 1 ô vuông trong hàng có giá trị lớn hơn hoặc bằng 2k .Bài toán ban đầu rằng bạn hãy tính toán xem dãy trên có được coi là tuyệt vời không. Nhưng để làm phức tạp trò chơi hơn, Phuong dãy số phương cho bao gồm cả số 0( có thể chọn số 2 hoặc 4).Yêu cầu hãy đếm số cách thay thế số 0 bằng 2 hoặc 4 để cho dãy số là dãy số tuyệt vời.Số cách có thể rất lớn nên hãy in ra số dư của phép chia kết quả cho 1e9+7(109 +7).

Ví dụ:

• arr={2,2,4,2,2,2,2},k = 4 ta có countPower(arr,k) = 1.
  Giải thích có 1 cách chọn duy nhất các số 0(đó là không chọn gì).
  Các bước di chuyển sẽ theo hướng sau:
  2...  →  4...  →  8...  →  8 2...  →  8 4..  →  8 4 2.  →  16.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C/C++, 2s với Java và C#, 2s với Python, Go và JavaScript.

• [Đầu vào] Array of Integer arr
  mảng arr chứa các số nguyên dương
  arr.size <= 2000
arr[i] = {0,2,4}

• [Đầu vào] Integer k
  3<=k<=1000

• [Đầu ra] Integer
  Phần dư của kết quả cho 1e9+7.