3805: 木棍(第六轮03)

鸡尾酒有一根长度为 x 的木棍，他可以根据这跟初始的木棍变出三根新的木棍， 变木棍的 规则如下：

变出来的三根新的木棍长度 必须严格递增 ，且新木棍的长度 newx    满足 x < newx  ≤ 4 * x。 （其中  x为初始木棍的长度）例如初始木棍长度为 x  = 2， 那么变出  [4,5,8]  三根木棍，  或者  [4,6,7]  三根木棍等方案都是合法的，但是变出 [3,5,5]  是不合法的，因为变出的三根  新木棍长度不是严格递增的； [4,6,9]  也是不合法的，因为  9   比 4 * x  = 8要大。

进行一次变幻之后，鸡尾酒总共就有四根木棍了。如果变幻结束之后可以从这四根木棍中选 出三根（只要有一种方案即可），使其能够作为一个三角形的三条边（即这三根木棍满足任 意两根的长度之和均大于另一根）， 那么称为这次变幻为一次“成功的变幻”。显然鸡尾酒有 很多种变幻木棍的方案，那么请问，假设初始的木棍长度为 x，鸡尾酒可以有多少种成功的 变幻？

由于答案可能很大，请输出答案对  10^9  + 7  求余后的结果。。

一行一个整数 x，表示初始木棍的长度。

输出一行一个正整数表示答案。

1

1