Xâu chỉ chứa các kí tự '0' hoặc '1' được gọi là xâu nhị phân. Xâu gồm các kí tự liên tiếp của S được gọi là xâu con của S. Xâu nhị phân S được gọi là không chứa xâu nhị phân P nếu P không phải là một xâu con của S.

Yêu cầu: Cho số nguyên n và xâu nhị phân P, hãy đếm số lượng xâu nhị phân độ dài n không chứa xâu nhị phân P.

Dữ liệu: Vào từ tệp văn bản BISTR.INP gồm hai dòng:

• Dòng đầu là số nguyên dương n (1≤n≤10^15);
• Dòng hai là xâu nhị phân P (độ dài xâu P không vượt quá 5).

  Kết quả: Ghi ra tệp văn bản BISTR.OUT một số nguyên là số lượng xâu thoả mãn yêu cầu bài toán chia lấy dư cho 20230928.

Ví dụ:

    BISTR.INP           BISTR.OUT           Giải thích
    3                   5                   Các xâu thoả mãn là:  "010","011","101","110","111".
    00

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: 1≤n≤20;
• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: 20<n≤10^5; </li>
• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: 10^5<n≤10^15.</li>