555 . 盧卡斯數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Williamm

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

45.5% (5/11)

Tags

apcsc apcsc-array

Description

盧卡斯數是一個很像斐波那契數的數列。但是，最初兩個盧卡斯數是 $L_0 = 2$ 和 $L_1 = 1$，而不是 $0$ 和 $1$。所以，盧卡斯數的性質與斐波那契數的性質有些不同。

盧卡斯數可以定義如下：
$$
L_n = L(n) = \begin{cases}
2, & \text{if }n = 0\\
1, & \text{if }n = 1\\
L(n-1)+L(n-2), & \text{if }n > 1\\
\end{cases}
$$

現在給你一個數字 $n$，請你求出 $L(n) \mod 1000000007$ 的結果

Input Format

一行包含一個非負整數 $n$

  • $n<100000$

Output Format

一行包含一個數字代表 $L(n) \mod 1000000007$ 的結果

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~27 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
Submit
Back to Top