Cho xâu nhị phân ~S = S_1 S_2 \dots S_m~ (~m \le 100~). Ta nói một xâu ~T~ nhận xâu ~S~ là xâu con đúng một lần nếu tồn tại duy nhất một vị trí ~k~ sao cho ~T_k = S_1, T_{k+1} = S_2, \dots, T_{k+m-1} = S_m~.

Cho số nguyên dương ~n \ge m~. Hãy xác định số lượng xâu nhị phân độ dài ~n~ không chứa xâu ~S~ là xâu con. Đưa ra kết quả theo module ~10^9 + 7~.

Yêu cầu: Tính số lượng xâu nhị phân độ dài ~n~ không chứa ~S~ làm xâu con theo modulo ~10^9 + 7~.

Input

• Dòng thứ nhất chứa số nguyên ~n~ (~n \le 10^5~).
• Dòng thứ hai chứa xâu ~S~ (~|S| \le 100~).

Output

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

Sample Input 1

4
01

Sample Output 1

5