U86873 小Y的精灵国机房之旅

小Y是一名航海家。一天，他乘船出海，不料船只失事，小Y也落难到了一个小岛上。在小Y绝望之际，他看到了一个小木屋。从木屋中走出两个人，他们一个叫小C，一个叫小H，他们是这个岛上的精灵。他们救助了困境中的小Y，并邀请他去精灵国玩。众所周知，精灵国是一个社会主义国家，所以里面的精灵都很社会(bushi)。小Y偶然发现，精灵国里也有机房。机房里面的电脑只有一排n个，并且和普通的电脑不同的是，每一个电脑都有自己的魔法标记。魔法标记有三种，分别是$Y$,$C$,$H$。我们定义两个电脑产生魔力，当且仅当这两个电脑的魔法标记分别为$Y$和$H$，且魔法标记为$Y$的电脑在魔法标记为$H$的电脑之前。值得一提的是，由于每台电脑的魔力有限，所以每台电脑只能和一台电脑产生魔力。而魔法标记为$C$的电脑很神奇，它可以根据使用者的想法让电脑的魔法标记变为$Y$或者$H$（但不可以不变）。小Y迫不及待地坐到了序号为1的电脑前面。但是小C和小H告诉他精灵国的机房有一个规矩，使用机房前必须回答一个问题：有多少种不同的方案使得机房中的电脑可以两两产生魔力。我们定义两种方案不同只需这两种方案中至少有一个相同位置的电脑的魔法标记不同，比如$YHYH$和$YYHH$就是不同的方案。但小Y对于这样的问题十分不擅长，所以他只能求助于你。由于答案有可能很大，所以对$1e9+7$取模。 数据保证一定有解

第一行 一个正整数$n$表示共有$n$台电脑 第二行 $n$个字符$Y$或$C$或$H$

一个正整数，表示最终的答案

对于30%的数据，n