题目内容
沉畀被妖怪抓走了，现在他的葫芦娃们想要去救他，但他们不清楚妖怪们的实力，于是他们需要养精蓄锐，待实力强大了再出发。他们决定最迟在第n天的时候将沉畀救出。
沉畀的葫芦娃藤每天早上都会结一个葫芦娃，每天晚上葫芦娃们会决定是否要一起去营救沉畀，由于葫芦娃们十分团结，他们会一起出动。然后会记录每天出动的葫芦娃个数。每天出动的个数组成一个序列。
现在，沉畀想要知道有多少种葫芦娃出动的序列。
输入描述
第一行输入一个整数n(1≤n≤1e5).
输出描述
输出葫芦娃出动的序列的个数，由于序列的个数可能非常大，输出对1e9 + 7取模。
样例1
输入
3
输出
4
样例说明
一共有四种序列分别是：
0 2 1，0 0 3，1 1 1，1 0 2
