奶⽜们学会了“0,1,2”这三个数字，他们没事的时候就会乱写。但是他们有⼀个奇怪的习性⸺从来不会连写两个0。现在Farmer John想知道，如果他们写⼀个⻓度为 N的串，⼀共有多少不同的可能。
第⼀⾏⼀个整数 N <=40 ，表⽰字符串的⻓度
⼀个整数，表⽰可能的串的个数。（答案可能很⼤,请⽤long long 计算与输出)
【样例解释】可能的串有:01,02, 10, 11, 12, 20, 21, 22。
对于40% 的数据，N <= 16
对于 100%的数据，N <= 40