令 \(f[0]=0\), \(f[1]=1\),  \(f[n]=f[n-1]+f[n-2], \forall n>1\)。 輸入非負整數 \(n\)，請輸出 \(f[n]\) 除以 \(p\) 的餘數。 \(p=1000000007, n<2^{31}\)。

輸入格式

輸入可能有多行，每一行有一個整數是一筆測資，最後一行以 \(-1\) 代表結束，不需要處理該筆測資。

輸出格式

每一行依序輸出計算結果。

範例輸入

6
123456789
100
-1

範例輸出

8
62791945
687995182