Start: Jun, 24, 2022 13:00:00
2022暑假短学期测试(补题)
End: Sep, 04, 2023 17:00:00
Time elapsed:
Time remaining:

tententen捉迷藏 3036

Time Limit:  1 s      Memory Limit:   256 MB
Submission:22     AC:6     Score:0

Description

众所周知ten是个小学生并且喜欢和大家玩捉迷藏游戏,但总是很快被抓住了。

一天ten灵机一动,把自己分身成了T、E、N三个英文字母,并且躲在了一串大写英文串内。但是ten的分裂技艺不精,她无法改变自己的相对位置。

现在请你输出最少几次选择T、E、N,保证可以让ten“原形毕露”。

相对位置指,如果选择的T、E、N下标分别为  $i,j,k$,则应满足 $i<j<k$ 。

只有当选择的T、E、N三个字符都是ten所分身的三个时,才能使ten“原形毕露”。

Input

输入两行一行。第一行为字符串长度。第二行为一串仅含大写英文字母的字符串 $S$。($|S| \leq \ 10^5$)

Output

最少几次可以保证抓住真正的T、E、N。如果无法找到,输出“ten,win!!!"(不包含双引)。由于结果可能比较大,只输出对 1e9+7 取余数的结果。

Samples

input
8 ATBENCEN
output
3
input
5 ANETB
output
ten,win!!!

Hint

样例1:可能存在的组合的下标分别是(245)(248)(278)这三种,所以最少3次便能保证找到躲起来的ten

样例2ANETB中不存在相对顺序为TEN的组合,所以无法找到,因此输出:ten,win!!!