Xét xâu nhị phân, tức là xâu chỉ chứa các ký tự trong tập ~{0, 1}~. Gọi ~k~ là số lượng xâu nhị phân độ dài ~n~ ~(1 \le n \le 10^4)~ chứa xâu ~S~ (độ dài không quá ~100~) như một xâu con (các ký tự liên tiếp) đúng một lần.

Yêu cầu: Hãy tính phần dư của kết quả chia ~k~ cho ~10^9+7~.

Input

• Dòng thứ nhất chứa số nguyên ~n~,
• Dòng thứ hai chứa xâu ~S~.

Output

• Một số nguyên – kết quả tìm được.

Sample Input

4
01

Sample Output

10