Olimpiade Sains Provinsi (OSP) 2019 - Komputer, Nomor 41

FIBONACCI

Pak Dengklek sangat suka dengan bilangan Fibonacci, yaitu bilangan yang dibentuk dengan rumus:

• Fibonacci(0) = 0
• Fibonacci(1) = 1
• Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), untuk n > 1

Karena Pak Dengklek senang bermain, ia memutuskan untuk membuat tebak-tebakan ke bebeknya dengan aturan sebagai berikut: ia akan bertanya sebanyak Q kali. Untuk setiap pertanyaan, ia akan mengatakan sebuah bilangan bulat positif N. Sang bebek harus menjawab bilangan fibonacci ke-N. Karena nilainya dapat sangat besar, maka program anda cukup memberikan hasil modulo bilangan tersebut dengan 10⁹ + 7. Bantulah sang bebek membuat program yang menjawab pertanyaan anehnya itu!

Format Masukan:
Baris pertama berisi sebuah bilangan bulat Q, banyaknya pertanyaan Pak Dengklek.
Q baris berikutnya masing-masing berisi sebuah bilangan N.

Format Keluaran:
Q baris, baris ke-i berisi jawaban dari pertanyaan ke-i.

Batasan:

• 1 ≤ Q ≤ 100.000
• 0 ≤ N ≤ 100.000

Contoh Masukan dan Keluaran:

3
10
3
7

55
2
13

5
11
15
8
4
9

89
610
21
3
34