小红和她的三个朋友们都有 天的暑假，她在暑假每天都找了其中一个朋友玩。暑假结束后，小红惊喜的发现，她跟每一个朋友都恰好玩了 天。 小红现在已经忘记了每天去找哪个朋友玩了，但她还记得没有连续 2 天都跟同一个朋友玩。 小红想知道有多少种可能的找朋友玩的序列。

输入描述:

第一行输入一个整数 。

输出描述:

输出一个整数表示答案。由于答案可能很大，输出答案对 取模的结果。