You have a long string \(S\) of Ms and Os and an integer \(K \geq 1\). Count the
number of ways of ways to decompose \(S\) into subsequences such that each
subsequence is MOOOO....O with exactly \(K\) Os, modulo \(10^9+7\).

Since the string is very long, you are not given it explicitly. Instead, you are
given an integer \(L\) (\(1 \leq L \leq 10^{18}\)), and a string \(T\) of length \(N\)
(\(1 \leq N \leq 10^6\)). The string \(S\) is the concatenation of \(L\) copies of the
string \(T\).

Problem credits: Dhruv Rohatgi

SCORING

• Inputs 5-7: \(K=1\), \(L = 1\)
• Inputs 8-10: \(K=2\), \(N\leq 1000\), \(L = 1\)
• Inputs 11-13: \(K=1\)
• Inputs 14-19: \(L = 1\)
• Inputs 20-25: No additional constraints.

Problem credits: Dhruv Rohatgi

The first line contains \(K\), \(N\), and \(L\).

The second line contains the string \(T\) of length \(N\). Every character is either
an M or an O.

It is guaranteed that the number of decompositions of \(S\) is nonzero.

Output the number of decompositions of string \(S\), modulo \(10^9+7\).

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > US Open > Gold