LPDSTR - Xâu LPD
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 5.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: CaiWinDao

"Tình yêu như nắng, nắng đưa em về, bên dòng suối mơ 
Nhẹ vương theo gió, gió mang câu thề, xa rời chốn xưa..."

Câu hát da diết của danh ca Tuấn Pearl vang lên làm thổn thức con tim mỏng manh của 2 fan trung thành là CaiWinDao và Cuom1999. Vừa thả hồn vào điệu nhạc trữ tình, CaiWinDao vừa thẫn thờ viết ra một xâu S độ dài k chỉ gồm các ký tự 'L', 'P' và 'D' in hoa (chữ cái đầu trong tên riêng của CaiWinDao, danh ca Tuấn Pearl và Cuom1999) - tất cả những gì có thể xuất hiện trong đầu cậu lúc đó. Cuom1999 thấy rằng đây là một cách rất hay để nguôi ngoai cơn seven tình nên cũng muốn viết ra một xâu độ dài n chỉ gồm các ký tự 'L', 'P', 'D' in hoa để trốn chạy khỏi tình cảnh "gọi tên em mãi, trong cơn mê này, mình nhớ thương nhau".  Vì trong tiềm thức của Cuom vẫn còn một chút cảm giác GATO không thể diễn giải thành lời đối với CaiWinDao nên cậu không muốn trong xâu mình viết ra có tồn tại một xâu con liên tiếp nào giống hệt với xâu S của CaiWinDao. Nhưng Cuom vẫn là một con người tự mâu thuẫn, dù không ưa nhau lắm nhưng cậu vẫn muốn trong xâu của mình có ít nhất ký tự 'L' - chữ cái đầu trong tên của CaiWinDao, như đã đề cập bên trên, và cũng là chữ cái đầu trong họ của người chị gái mưa đã làm Cuom lâm vào cảnh dở khóc dở cười này.

Trước khi đặt bút viết ra xâu của mình, theo bản năng Toán học sẵn có, Cuom1999 muốn biết có tất cả bao nhiêu xâu ký tự khác nhau thỏa mãn tất cả các điều kiện trên:

-Chỉ gồm các ký tự 'L', 'P', 'D' in hoa.

-Độ dài đúng bằng n.

-Không tồn tại xâu con liên tiếp nào giống hệt với xâu S.

-Có chứa ít nhất m ký tự 'L'.

Vì lý trí đã bị cơn say tình làm lu mờ, Cuom đành phải tìm tới cao thủ Ami để nhờ bạn ấy tính toán hộ kết quả đó. Thật không may là tình cảnh của Ami cũng không khá hơn Cuom bao nhiêu nên bạn ấy tiếp tục phải nhờ đến sự trợ giúp của các bạn. Cuom và Ami vẫn còn chút tỉnh táo để nhận thức được rằng kết quả nhận được có thể rất lớn nên họ chỉ cần các bạn đưa ra phần dư khi chia kết quả cho 109+7.

Dữ liệu vào:

Dòng đầu chứa ba số nguyên nm và k. (1 <= m , k <= n <= 300).

Dòng sau chứa xâu S độ dài k do CaiWinDao viết ra.

Kết quả:

Một số nguyên duy nhất là kết quả cần tìm.

Ví dụ

Input

3 1 2
LP

Output

13

Giải thích

13 xâu thỏa mãn là "DDL", "DLD", "DLL", "DPL",  "LDD", "LDL", "LDP", "LLD", "LLL", "PDL", "PLD", "PLL" và "PPL".

 

Ví dụ

Back to Top