Một SEED là một xâu chỉ gồm ~2~ loại ký tự "~1~" hoặc "~*~" thỏa điều kiện bắt đầu và kết thúc của SEED là "1". Một SEED ~s~ được gọi là "~hit~" được xâu nhị phân ~x~ độ dài ~N~ nếu tồn tại một vị trí ~i~ trên xâu ~x~ thỏa mãn: Nếu ký tự thứ ~k~ của xâu ~s~ bằng "1" thì ký tự thứ ~i+k-1~ của ~x~ cũng bằng "1".

Ví dụ:

~1*1~ có thể "~hit~" được các xâu 0101100, 1110000, 1010111 nhưng không "~hit~" được xâu 0100010.

Yêu cầu:

Cho ~N~ và một SEED ~s~, đếm số lượng xâu nhị phân độ dài ~N~ mà ~s~ "~hit~" được.

Input

• Dòng 1: chứa số ~N~ (~N ≤ 50~)
• Dòng 2: ghi SEED ~s~ là một xâu chỉ gồm ~2~ loại ký tự "~1~" và "~*~"

Output

• Gồm một dòng, chứa một số là số lượng xâu nhị phân mà ~s~ có thể "~hit~" được.

Sample Input 1

10
1

Sample Output 1

1023

Sample Input 2

3
1*1

Sample Output 2

2

Giới hạn

Subtask 1: ~n ≤ 20~ [~40~ tests]

Subtask 2: ~length(s) ≤ 15~ [~30~ tests]

Subtask 3: ~length(s) ≤ 30~ và số ký tự ~*~ trong ~s~ không vượt quá số ký tự ~1~. [~30~ tests]

Nguồn: Trại đông Bảo Lộc 2021 - Thầy Đỗ Đức Đông