B-Brilliant Idea_2023年第六届广西大学生程序设计竞赛（正式赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

One day, a brilliant idea came to Colin's mind.
Given a string $S$ with length $n$ (indexed from $0$ to $n-1$ ) consisting of lowercase letters.
Let $S_i$ denotes the character of $S$ with index $i$ , e.g. let $S=$ abc then $S_0=$ a and $S_1=$ b.
Let $S[l:r]$ denotes the substring of $S$ with index form $l$ to $r$ , e.g. let $S=$ abc then $S[1:2]=$ bc .

Now we play a game on the string. You want to take as many turns successfully as you can.

In one turn, you should:

first choose two integers $l,r$ satisfying $0\le l<r< n$ and $S[l:r]$ has at least two different characters (i.e. exist two different integers $x,y\in[l, r]$ satisfy $S_x\not =S_y$ ). If you cannot find such two integers $l,r$ , you fail in this turn, and the game ends.
then choose an integer $p\in[l,r]$ , change all the characters $S_i\ (i\in[l, r])$ into $S_p$ ; then you take this turn successfully.

For example, let $S=$ abc and choose $l=1,r=2,p=2$ , then after this turn, $S$ becomes acc .
Colin wants to ask you, at most how many turns can be successfully taken on string $S$ ?

Eva thought that's too easy for you, so she upgraded this problem to a counting problem. Let $ans_S$ denotes the answer to the above question for string $S$ , you need to count that among all strings with length $n$ consisting of lowercase letters:
1. how many strings satisfy $ans_S=0$ ?
2. how many strings satisfy $ans_S>0$ and $ans_s$ is finite?
3. how many strings satisfy $ans_S$ is infinite?

输入描述:

First line a single integer  , representing the length of the string.

输出描述:

A single line contains three integers.
The first one represents the number of strings satisfying  , module  .
The second one represents the number of strings satisfying  and  is finite, module  .
The third one represents the number of strings satisfying  is infinite, module  .

示例1

输入

复制

输出

复制

26 650 0

说明

There are  strings with length  satisfies , and their  .
For the rest strings with length  , it's easy to see that you can only take  turn successfully, so their   .