Đêm Giáng Sinh đang đến rất gần, và sau nhiều trò chơi hôm nay, ABNL muốn dành tặng phần quà đặc biệt cho các bạn đã đến được map cuối này. ABNL đã mời đến nhà ảo thuật gia J99, cùng với nhiều hộp quà thú vị.

Nhưng trước đó, ảo thuật gia J99 muốn thực hiện một màn ảo thuật gửi tặng các bạn. J99 đem ra một nhóm hộp quà bí ẩn. Những chiếc hộp này không được đánh dấu, và một số trong chúng chứa các món quà giống hệt nhau. Đặc biệt, có những vị trí trên sàn chỉ là chỗ trống – không có hộp nào cả. J99 quyết định biến tình huống này thành một trò chơi thử thách.

J99 chơi một trò chơi bằng cách nhặt \(K\) hộp quà ngẫu nhiên trên sàn, tráo đổi vị trí của chúng và đặt lại xuống. Tuy nhiên, không hộp nào được đặt lại vị trí cũ, và sau khi tráo đổi, trạng thái cuối cùng của sàn phải trông giống hệt như ban đầu.

J99 sẽ thưởng cho các bạn một ngôi sao tinh tú nếu giải được bài toán này. Hãy tính xác suất mà ảo thuật gia J99 có thể thực hiện được trò chơi này. Nếu xác suất đó có thể tính được, biểu diễn nó dưới dạng \(p \cdot q^{-1} \pmod{998244353}\), trong đó \(\frac{p}{q}\) là xác suất dưới dạng phân số tối giản.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) \((2 \leq N \leq 1000000)\) và \(K\) \((1 \leq K < N)\) - số lượng vị trí trên sàn và số lượng hộp quà sẽ được nhặt.
• Dòng thứ hai chứa một chuỗi độ dài \(N\), gồm các ký tự:
• '.' đại diện cho vị trí trống
• 'a'-'z' và '0'-'9' đại diện cho các loại hộp quà

Output

• Một số nguyên duy nhất là \(p \cdot q^{-1} \pmod{998244353}\), trong đó \(\frac{p}{q}\) là xác suất thành công

Example

10 1
..a.r3o...

0

4 2
qq..

1

10 2
..i.c.p.c.

166374059