Tránh mẫu

Xâu nhị phân \(S\) được gọi là tránh mẫu nhị phân \(P\) , nếu xâu \(P\) không xuất hiện trong \(S\).

Cho \(n\) và xâu nhị phân \(P\), hãy đếm số lượng xâu nhị phân \(S\) độ dài \(n\) tránh mẫu \(P\).

Input

Gồm nhiều dòng, mỗi dòng chứa số nguyên \(n\) và xâu nhị phân \(P\) (độ dài xâu \(P\) không vượt quá \(5\)).

Output

Gồm nhiều dòng, mỗi dòng là đáp án tương ứng với bộ dữ liệu vào, vì kết quả có thể rất
lớn nên kết quả đưa ra là phần dư cho \(111539786\).

Example

3 00

5

Scoring

Subtask \(1\) tương ứng với \(30\%\) số điểm: \(n \leq 10\).

Subtask \(2\) tương ứng với \(30\%\) số điểm: \(n \leq 10^5\).

Subtask \(3\) tương ứng với \(40\%\) số điểm: \(n \leq 10^{15}\).