Một dãy số f được tạo ra với số thứ n có dạng f(n) = f(n-1) * f(n-2) + f(n-3) với f(1) = 1, f(2) = 1, f(3) = 2. Hãy viết chương trình tìm số thứ n của dãy f. Vì kết quả có thể rất lớn trả về giá trị số đó mod 10 ** 9 + 7.
Ví dụ:
Với n = 1 thì đầu ra của f(n) = 1.
Với n = 2 thì đầu ra của f(n) = 1.
Với n = 3 thì đầu ra của f(n) = 2.
Với n = 4 thì đầu ra của f(n) = 3.
n = int(input())
def f(n):
if n==1: return 1
if n==2: return 1
if n==3: return 2
if n==4: return 3
x1=1
x2=1
x3=2
x=3
for i in range(4,n):
x1,x2,x3=x2,x3,x
x=x2*x3+x1
return x%(10**9+7)
print(f(n))