Farmer John刚刚买了一台可编程的拖拉机。为了让拖拉机运转起来，他定义了一个长度为N(1≤N≤100000)的字符串来对拖拉机进行编程，字符串仅由F,L,R三种字符组成。其中F代表拖拉机前进一个单位，L和R分别表示向左和向右转90度。最开始拖拉机位于原点(0,0)的位置，并且面朝北。
FJ完成对拖拉机的编程后，他意识到在字符串中有一个字符可能输入错了，但是他不记得是哪一个字符错了。比如，他字符串中有一个字符应该输入R，但是他可能输入是R或者是L。
请计算出最终拖拉机结束工作时的位置可能有多少个？（最终位置的朝向可以不用关心）

一行，一个字符串，表示FJ用来给拖拉机编程的字符串。

一行，一个整数，表示拖拉机按照输入中给出的命令字符串进行工作，最终结束工作时，拖拉机可能的位置的数量

样例说明：
输入的字符串为FF，有4中可能错误的字符串，分别是:FL,FR,LF,RF,所以这四个命令字符串会导致拖拉机最终的位置分别是(0,1)、(0,1)、(-1,0)、(1,0),所以答案是3.

快速排序 USACO 2012 level4