Trong một vương quốc xa xôi, có một vị vua rất đam mê toán học và những câu đố nhị phân. Ngày nọ, ông tổ chức một cuộc thi để tìm ra người có thể tạo ra nhiều xâu nhị phân nhất mà không chứa một mẫu nhị phân cấm do ông chọn. Mẫu nhị phân này có thể là bất kỳ chuỗi nào không vượt quá độ dài 5.

Người chơi được cung cấp một số nguyên ~n~, đại diện cho độ dài của xâu nhị phân, và mẫu nhị phân cấm ~P~. Nhiệm vụ của họ là đếm số lượng xâu nhị phân ~S~ có độ dài ~n~ mà không chứa mẫu ~P~.

Yêu cầu: Hãy viết chương trình đếm số lượng xâu nhị phân ~S~ độ dài ~n~ tránh mẫu ~P~. Vì kết quả có thể rất lớn, bạn cần đưa ra phần dư của kết quả cho ~111539786~.

Input

• Dòng 1: Số nguyên ~n~.
• Dòng 2: Xâu nhị phân bị cấm ~P~.

Output

• Một số nguyên duy nhất là đáp án, là phần dư của kết quả cho ~111539786~.

Sample Input 1

3
00

Sample Output 1

5