Tổng dấu thay đổi

Cho hai số nguyên dương $a,b$ và một dãy $s_0,s_1,\dots ,s_n$ trong đó mỗi $s_i\in \{1,-1\}$.

Dãy $s$ có tính tuần hoàn với chu kỳ $k$, nghĩa là $s_i=s_{i-k}$ với mọi $k\le i\le n$. Ngoài ra, $k$ là ước của $n+1$.

Hãy tính giá trị sau theo modulo ${10}^9+9$:

$$\sum _{i=0}^n{s}_i·a^{n-i}·b^i$$

Lưu ý: kết quả phải là phần dư không âm sau khi chia cho ${10}^9+9$.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n,a,b,k$.
• Dòng thứ hai chứa một xâu độ dài $k$ gồm các ký tự + và -. Nếu ký tự thứ $i$ (đánh chỉ số từ 0) là + thì $s_i=1$, ngược lại $s_i=-1$. Chỉ $k$ phần tử đầu được cho, phần còn lại suy ra từ tính tuần hoàn.

Dữ liệu ra

In ra một số nguyên duy nhất là phần dư không âm của tổng trên khi chia cho ${10}^9+9$.

Ràng buộc

• $1\le n\le {10}^9$
• $1\le a,b\le {10}^9$
• $1\le k\le {10}^5$
• $k$ chia hết $n+1$.

Ví dụ