"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 cuom1999 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 cuom1999 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 \(m\) 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 cuom1999 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ờ, cuom1999 đà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 cuom1999 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. cuom1999 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 \(10^9+7\).

Input:

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

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

Output:

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.