1717: 界面越花 编程越拉

众所周知，“界面越花编程越拉”，不过小m的离散数学学的并不是很好，所以当小m听到了这句话之后，小m认为只要自己的界面变得简朴，自己的编程就会越来越好了。小m想到了两个办法让自己当前界面的华丽值下降：

1、 他通过修改编辑器的界面，使华丽值下降1点。

2、 他通过更换别的更简朴的编译器，使华丽值变成当前的二分之一(下取整)；

现给出小m的初始华丽值n，请输出使华丽值变为0的方案数。由于方案数可能过多，所以请对最终答案取模1e9+7。

例如:3->0的方案数有6种,"111","112","121","122","21","22"，所以你只需要输出6就可以了。

一个正整数n。(n <= 1e5)

一个整数。

3

6