Wesley's Anger Contest 6 Problem 4 - Runway Lights

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.5s
Memory limit: 256M

Author:
Problem types

Wesley is going on a trip to the North!

But first, he needs a proper runway for takeoff. The runway is marked with festive safety lights and can be represented as a sequence of NN light bulbs repeated KK times, with each safety light lit up with a specific colour. The colour of the light bulbs can each be represented as an uppercase letter, forming a string SS of length NN. The complete runway can be represented as a string of length N \cdot KN \cdot K.

Due to the costs associated with maintaining the full runway, Wesley has decided to remove some safety lights. Through careful consideration, the new runway should have exactly 33 safety lights forming the pattern WAC. There are many ways to do this, and Wesley is interested in the number of distinct new runways that form the pattern WAC.

The new runway is formed by removing a nonnegative amount of safety lights from the original runway without changing the relative positions of the remaining safety lights. Two runways are considered to be different if there is at least one safety light kept that is located in a different position of the original runway.

As the runway director, please determine and report the number of valid new runways to Wesley! Since the answer could get very large, output the answer modulo 998\,244\,353998\,244\,353.

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N,K \le 200\,0001 \le N,K \le 200\,000

Subtask 1 [10%]

1 \le N \le 1001 \le N \le 100
1 \le K \le 31 \le K \le 3

Subtask 2 [24%]

1 \le N,K \le 3001 \le N,K \le 300

Subtask 3 [66%]

No additional constraints.

Input Specification

The first line will contain two integers NN and KK, the number of light bulbs in the pattern SS and the number of repeats of the pattern SS to form the complete runway.

The second and final line will contain a string of NN characters SS, consisting of uppercase letters of the alphabet.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer representing the number of distinct new runways that form the pattern WAC, modulo 998\,244\,353998\,244\,353.

Sample Input 1

5 1
WABCA

Sample Output 1

1

Sample Explanation 1

The full runway sequence of lights is WABCA.

There is 11 way to form a distinct new runway:

  • Remove the third and fifth safety light, forming WAC.

Sample Input 2

5 2
WABCA

Sample Output 2

5

Sample Explanation 2

The full runway sequence of lights is WABCAWABCA.

There are 55 ways to form a distinct new runway:

  • Keep the safety lights at the indices 11, 22, and 44
  • Keep the safety lights at the indices 11, 22, and 99
  • Keep the safety lights at the indices 11, 55, and 99
  • Keep the safety lights at the indices 11, 77, and 99
  • Keep the safety lights at the indices 66, 77, and 99

Comments

There are no comments at the moment.