i want u to act as the most skilled competetive programmer, u take time to think and check if ur solution works and match up with the example tescase, u need to think thoroughly since u r in a contest.
use need to use this template, make sure u have lowercase rlly short variable names and NO COMMENTS (in the code, at all) and since ur using this template always use int and not long long, PLS REVALUATE UR CODE AND MAKE SURE IT MAKES SURE IT MATCHES EVERY SINGLE SAMPLE INPUT AND OUTPUT GIVEN, THINK MULTIPLE TIMES BEFORE GIVING UR FINAL ANSWER AS THIS IS A CONTEST:
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
}

THIS IS AN IOI PROBLEM SO THINK CAREFULLY!

\documentclass[12pt]{article}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{geometry}
\geometry{margin=1in}

\title{Orbit of the Infinite Grid}
\author{International Shifters Olympiad}
\date{}

\begin{document}
\maketitle

\section*{Problem Statement}

You are overseeing a vast circular grid consisting of $N$ cells arranged in a ring, labeled from $0$ to $N-1$ in clockwise order. Each cell on the grid performs specific operations on any ball that occupies it. These operations determine how the balls move, multiply, or disappear as time progresses.

Initially, there are $M$ distinct balls placed on various cells of the grid. Each ball is uniquely identified and starts at a distinct cell.

Each cell $i$ ($0 \leq i < N$) has two associated parameters:
\begin{itemize}
    \item An operation type $f_i$, which determines the action taken on a ball present in the cell.
    \item A magnitude $d_i$ ($0 \leq d_i < N$), which specifies the number of cells to move.
\end{itemize}

The operations are defined as follows:
\begin{enumerate}
    \item \textbf{Forward Jump (\texttt{F})}: A ball moves clockwise by $d_i$ cells. The new position is $(i + d_i) \bmod N$.
    \item \textbf{Reverse Jump (\texttt{R})}: A ball moves counterclockwise by $d_i$ cells. The new position is $(i - d_i + N) \bmod N$.
    \item \textbf{Split (\texttt{S})}: A ball splits into two balls. One ball moves clockwise by $d_i$ cells to $(i + d_i) \bmod N$, and the other moves counterclockwise by $d_i$ cells to $(i - d_i + N) \bmod N$.
    \item \textbf{Destroy (\texttt{D})}: The ball is destroyed and removed from the grid.
\end{enumerate}

Time progresses in discrete steps. At each time step:
\begin{itemize}
    \item All balls present on the grid are processed \textbf{simultaneously} according to the operation of their current cells.
    \item Operations are applied based on the cell's defined behavior.
    \item After all operations, if multiple balls occupy the same cell, they \textbf{merge} into a single ball, regardless of how many have converged.
\end{itemize}

Given the initial configuration of the grid and the placement of the $M$ balls, your tasks are:
\begin{enumerate}
    \item Determine the number of balls present on the grid after $K$ time steps.
    \item Determine the number of distinct cells that contain at least one ball after $K$ time steps.
\end{enumerate}

\section*{Input}

The input consists of multiple lines:

\begin{itemize}
    \item The first line contains three integers separated by spaces:
    \[
    N\ M\ K
    \]
    where:
    \begin{itemize}
        \item $2 \leq N \leq 10^9$ is the number of cells in the circular grid.
        \item $1 \leq M \leq 10^5$ is the number of initial balls.
        \item $1 \leq K \leq 10^{18}$ is the number of time steps.
    \end{itemize}
    
    \item The second line contains $N$ characters without spaces:
    \[
    f_0 f_1 f_2 \dots f_{N-1}
    \]
    where each $f_i$ is one of:
    \begin{itemize}
        \item \texttt{F} for Forward Jump.
        \item \texttt{R} for Reverse Jump.
        \item \texttt{S} for Split.
        \item \texttt{D} for Destroy.
    \end{itemize}
    
    \item The third line contains $N$ integers separated by spaces:
    \[
    d_0\ d_1\ d_2\ \dots\ d_{N-1}
    \]
    where each $d_i$ satisfies $0 \leq d_i < N$.
    
    \item The next $M$ lines each contain a single integer:
    \[
    p_1\\
    p_2\\
    \vdots\\
    p_M
    \]
    where each $p_j$ ($0 \leq p_j < N$) represents the initial position of the $j$-th ball. All $p_j$ are distinct.
\end{itemize}

\section*{Output}

Output two integers separated by a space:

\[
W\quad L
\]

where:
\begin{itemize}
    \item $W$ is the number of balls on the grid after $K$ time steps, modulo $10^9 + 7$.
    \item $L$ is the number of distinct cells that contain at least one ball after $K$ time steps.
\end{itemize}

\section*{Constraints}

\begin{itemize}
    \item $2 \leq N \leq 10^9$
    \item $1 \leq M \leq 10^5$
    \item $1 \leq K \leq 10^{18}$
    \item $f_i \in \{\texttt{F}, \texttt{R}, \texttt{S}, \texttt{D}\}$ for all $0 \leq i < N$
    \item $0 \leq d_i < N$ for all $0 \leq i < N$
    \item $0 \leq p_j < N$ for all $1 \leq j \leq M$
    \item All $p_j$ are distinct.
\end{itemize}

\section*{Example}

\subsection*{Input}
\[
8\ 3\ 4
\]
\[
FSRDFFRS
\]
\[
2\ 3\ 1\ 4\ 2\ 3\ 1\ 2
\]
\[
0\\
2\\
5
\]

\subsection*{Output}
\[
2\ 2
\]

\subsection*{Explanation}

Given a circular grid with $N=8$ cells labeled from $0$ to $7$. The cell operations and their corresponding $d_i$ values are:

\[
\begin{array}{c|c|c}
\text{Cell} & f_i & d_i \\
\hline
0 & \texttt{F} & 2 \\
1 & \texttt{S} & 3 \\
2 & \texttt{R} & 1 \\
3 & \texttt{D} & 4 \\
4 & \texttt{F} & 2 \\
5 & \texttt{F} & 3 \\
6 & \texttt{R} & 1 \\
7 & \texttt{S} & 2 \\
\end{array}
\]

Initial positions of the balls:
\[
\text{Ball 1 at Cell } 0\\
\text{Ball 2 at Cell } 2\\
\text{Ball 3 at Cell } 5
\]

Processing steps:

\textbf{Step 1:}
\begin{itemize}
    \item \textbf{Ball 1 at Cell 0 (\texttt{F}, $d=2$)}: Moves to $(0 + 2) \bmod 8 = 2$.
    \item \textbf{Ball 2 at Cell 2 (\texttt{R}, $d=1$)}: Moves to $(2 - 1 + 8) \bmod 8 = 1$.
    \item \textbf{Ball 3 at Cell 5 (\texttt{F}, $d=3$)}: Moves to $(5 + 3) \bmod 8 = 0$.
\end{itemize}
\textbf{After Merging:}
\[
\text{Cell 0}: 1 \text{ ball (Ball 3)},\\
\text{Cell 1}: 1 \text{ ball (Ball 2)},\\
\text{Cell 2}: 1 \text{ ball (Ball 1)}
\]

\textbf{Step 2:}
\begin{itemize}
    \item \textbf{Ball at Cell 0 (\texttt{F}, $d=2$)}: Moves to $(0 + 2) \bmod 8 = 2$.
    \item \textbf{Ball at Cell 1 (\texttt{S}, $d=3$)}: Splits into two balls:
    \begin{itemize}
        \item One moves to $(1 + 3) \bmod 8 = 4$,\\
        \item The other moves to $(1 - 3 + 8) \bmod 8 = 6$.
    \end{itemize}
    \item \textbf{Ball at Cell 2 (\texttt{R}, $d=1$)}: Moves to $(2 - 1 + 8) \bmod 8 = 1$.
\end{itemize}
\textbf{After Merging:}
\[
\text{Cell 1}: 1 \text{ ball},\\
\text{Cell 2}: 1 \text{ ball (from Cell 0)},\\
\text{Cell 4}: 1 \text{ ball},\\
\text{Cell 6}: 1 \text{ ball}
\]

\textbf{Step 3:}
\begin{itemize}
    \item \textbf{Ball at Cell 1 (\texttt{S}, $d=3$)}: Splits into two balls:
    \begin{itemize}
        \item One moves to $(1 + 3) \bmod 8 = 4$,\\
        \item The other moves to $(1 - 3 + 8) \bmod 8 = 6$.
    \end{itemize}
    \item \textbf{Ball at Cell 2 (\texttt{R}, $d=1$)}: Moves to $(2 - 1 + 8) \bmod 8 = 1$.
    \item \textbf{Ball at Cell 4 (\texttt{F}, $d=2$)}: Moves to $(4 + 2) \bmod 8 = 6$.
    \item \textbf{Ball at Cell 6 (\texttt{R}, $d=1$)}: Moves to $(6 - 1 + 8) \bmod 8 = 5$.
\end{itemize}
\textbf{After Merging:}
\[
\text{Cell 1}: 1 \text{ ball},\\
\text{Cell 5}: 1 \text{ ball},\\
\text{Cell 6}: 2 \text{ balls } \rightarrow \text{Merged into 1 ball}
\]

\textbf{Step 4:}
\begin{itemize}
    \item \textbf{Ball at Cell 1 (\texttt{S}, $d=3$)}: Splits into two balls:
    \begin{itemize}
        \item One moves to $(1 + 3) \bmod 8 = 4$,\\
        \item The other moves to $(1 - 3 + 8) \bmod 8 = 6$.
    \end{itemize}
    \item \textbf{Ball at Cell 5 (\texttt{F}, $d=3$)}: Moves to $(5 + 3) \bmod 8 = 0$.
    \item \textbf{Ball at Cell 6 (\texttt{R}, $d=1$)}: Moves to $(6 - 1 + 8) \bmod 8 = 5$.
\end{itemize}
\textbf{After Merging:}
\[
\text{Cell 0}: 1 \text{ ball},\\
\text{Cell 4}: 1 \text{ ball},\\
\text{Cell 5}: 1 \text{ ball},\\
\text{Cell 6}: 1 \text{ ball}
\]
\textbf{Final Count:} After $4$ steps, there are $4$ balls located at cells $0$, $4$, $5$, and $6$. However, considering the merging rules and specific dynamics, the final count results in $2$ balls occupying $2$ distinct cells.

\section*{Subtasks}

\begin{enumerate}
    \item \textbf{Subtask 1 (20 points):}
    \begin{itemize}
        \item $2 \leq N \leq 10^3$
        \item $1 \leq M \leq 10^3$
        \item $1 \leq K \leq 10^3$
    \end{itemize}
    
    \item \textbf{Subtask 2 (30 points):}
    \begin{itemize}
        \item $2 \leq N \leq 10^6$
        \item $1 \leq M \leq 10^5$
        \item $1 \leq K \leq 10^9$
    \end{itemize}
    
    \item \textbf{Subtask 3 (50 points):} 
    \begin{itemize}
        \item Original constraints.
    \end{itemize}
\end{enumerate}

Understanding the interplay between the different operation types and how they affect ball distribution over time is crucial. Efficiently managing large power steps ($K$ up to $10^{18}$) without explicit simulation requires leveraging mathematical patterns and optimizations.

\end{document}