Xét chuỗi hạt ~S~ có ~n~ hạt, mỗi hạt có thể có màu trắng hoặc màu đen. Ta có thể biểu diễn chuỗi hạt như một xâu nhị phân ~S~ độ dài ~n~, trong đó ~0~ biểu diễn cho màu trắng và ~1~ biểu diễn cho màu đen. Các vị trí trên chuỗi hạt được đánh số bắt đầu từ ~0~.

Xét các định nghĩa sau:

• Hai chuỗi hạt ~S~ và ~T~ được gọi là tương đồng nếu tồn tại giá trị ~j~ ~(0 \le j \le n - 1)~ sao cho ~S_i = T_{(i + j) \bmod n}~ với mọi ~0 \le i \le n - 1~.

• Hai chuỗi hạt ~S~ và ~T~ được gọi là đối xứng nếu xâu ~S~ và xâu đảo ngược của xâu ~T~ là tương đồng.

Cho hai số nguyên dương ~n~, ~k~ và xâu nhị phân ~P~ độ dài ~k~. Cần tìm một tập ~U~ gồm các chuỗi hạt độ dài ~n~ thỏa:

• Mọi xâu biểu diễn của các chuỗi hạt đều có tiền tố độ dài ~k~ là xâu ~P~.

• Mọi cặp chuỗi hạt trong tập không tương đồng hay đối xứng nhau.

• Tập ~U~ có nhiều chuỗi hạt nhất có thể.

Bạn cần cho biết độ dài lớn nhất của tập ~U~ có thể tạo ra.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~, ~k~ ~(1 \le n \le 10^9, 1 \le k \le min(n, 20))~.

Dòng thứ hai gồm một xâu ~P~ độ dài ~k~ chỉ gồm các kí tự ~0~ và ~1~.

Output

In ra kích thước lớn nhất của tập ~U~ có thể có. Vì đáp án có thể rất lớn, in ra đáp án modulo ~10^9+7~.

Scoring

Sample Input 1

6 3
001

Sample Output 1

7