ছোট্ট মিকি সূর্যমুখীর বীজের প্যাটার্ন নিয়ে গবেষণা করছে। সে খবরের কাগজে পড়েছে যে, সূর্যমুখীর প্যাটার্নের সাথে ফিবোনাচ্চি ধারার একটা যোগসূত্র আছে।

ফিবোনাচ্চি ধারা হচ্ছে পূর্ণসংখ্যার একটি ধারা যার প্রথম দুটি পদ হচ্ছে ০ এবং ১। এরপরের পদগুলো এই রিকারেন্স রিলেশন দিয়ে বলে ফেলা যায়: F(n) = F(n-1) + F(n-2)

কয়েকটি উদাহরণ নিম্নরূপ:

F(1) = 0

F(2) = 1

F(3) = F(2) + F(1) = 0 + 1 = 1

F(4) = F(3) + F(2) = 1 + 1 = 2

F(5) = F(4) + F(3) = 2 + 1 = 3

F(6) = F(5) + F(4) = 3 + 2 = 5

তুমি ব্যাপারটা ধরতে পেরেছো, তাই না? মিকিকে তার গবেষণা সফলভাবে চালানোর জন্য ধারাটির n তম পদ বের করতে হবে। তার গবেষণার ধরণটাই এমন, যে তার পুরো উত্তরটাও দরকার নেই। তার বদলে উত্তরকে 10^9+7 দিয়ে মড করলে যেই মানটি পাওয়া যায়, সেটিই তার দরকার।

তোমার কাজ তাকে সাহায্য করা।

Little Micky is researching patterns on Sunflower seeds. He read on a newspaper once that the pattern on sunflower has relation with Fibonacci sequence. He wondered how?

A Fibonacci sequence is a integer number sequence where the first two terms are 0 and 1. After that, the following terms are defined using the recurrence relation F(n) = F(n-1) + F(n-2).

F(1) = 0
F(2) = 1
F(3) = F(2) + F(1) = 0 + 1 = 1
F(4) = F(3) + F(2) = 1 + 1 = 2
F(5) = F(4) + F(3) = 2 + 1 = 3
F(6) = F(5) + F(4) = 3 + 2 = 5

You get the idea right? But in order to research the sequence, Micky needs to find the nth term of the sequence. Due to the nature of his research, he doesn't need the exact value of the term. Instead he needs the answer modulo 10^9+7.

Can you please help him?