Đếm Xâu Có Mẫu Bắt Buộc · canuc80k2137

Cho số nguyên $N$ và mẫu chữ hoa $P$ . Hãy đếm số xâu độ dài đúng $N$ trên bảng $26$ chữ A đến $Z$ có $P$ xuất hiện ít nhất một lần như một đoạn liên tiếp. Mỗi xâu được tính một lần, bất kể có bao nhiêu occurrence.

Input

Dòng đầu chứa $N$ .
Dòng thứ hai chứa $P$ .

Output

In đáp án modulo $1000000007$ .

Constraints

$1 \leq N \leq 1000$ .
$1 \leq ∣ P ∣ \leq 100$ ; $P$ chỉ gồm $A, \dots, Z$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 4$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
AB

Output

Giải thích: Mẫu có thể nằm ở vị trí $1$ hoặc $2$ . Có $26$ xâu dạng ABx và $26$ xâu dạng xAB; hai nhóm không giao nhau, nên tổng là $52$ .

Phân tích: Đếm xâu chữ hoa độ dài N chứa pattern P ít nhất một lần, modulo 10^9+7.
Phân tích: Dựng transition KMP cho các trạng thái 0..|P|. Trạng thái |P| là hấp thụ, biểu diễn P đã xuất hiện. DP theo từng vị trí và 26 ký tự; đáp án là số đường đi kết thúc ở trạng thái hấp thụ.
Thuật toán: 1. Chuyển input về trạng thái hoặc biểu diễn đối sánh nêu trên. 2. Tính prefix-function và các transition cần thiết. 3. Duyệt dữ liệu hoặc các trạng thái DP, cập nhật đúng quy tắc biên và occurrence chồng lấn. 4. In kết quả theo đúng output contract; với output không duy nhất, checker xác minh tính hợp lệ và tối ưu.
Chứng minh: Trước khi match, trạng thái KMP lưu đúng tiền tố dài nhất của P đang là hậu tố; khi đạt |P|, occurrence đã tồn tại và trạng thái hấp thụ giữ sự kiện đó. Mỗi xâu tương ứng duy nhất một đường đi và được cộng một lần, nên các đường kết thúc ở |P| đúng bằng tập cần đếm.
Độ phức tạp: O(26N|P|) thời gian và O(|P|) bộ nhớ DP.