AT_abc006_2 [ABC006B] トリボナッチ数列

[problemUrl]: https://atcoder.jp/contests/abc006/tasks/abc006_2 トリボナッチ数列というものがあります。この数列は3つ前までの数字を足したものです。 厳密には、 1\. $ a_1\ =\ 0 $, $ a_2\ =\ 0 $, $ a_3\ =\ 1 $ 2\. $ a_n\ =\ a_{n-1}\ +\ a_{n-2}\ +\ a_{n-3} $ と定義されています。参考までに、トリボナッチ数列表を掲載します。 | # | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ | $a_6$ | $a_7$ | $a_8$| ...... | $a_n$ | | :--- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :--------------------------------------- | | 値 | 0 | 0 | 1 | 1 | 2 | 4 | 7 | 13 | ...... | $a_{n−1}+a_{n−2}+a_{n−3}$ | この数列の第 $ n $ 項、$ a_n $ を $ 10007 $ で割った余りを求めてください。 入力は以下の形式で標準入力から与えられる。 > $ n $ 整数 $ n(1≦n≦10^6) $ が $ 1 $ 行で与えられる。 トリボナッチ数列の第 $ n $ 項、$ a_n $ を $ 10007 $ で割った余りを $ 1 $ 行で出力してください。 また、出力の末尾には改行を入れること。 ``` 7 ``` ``` 7 ``` - $ 7 $ 番目のトリボナッチ数は $ 7 $ です。 ``` 1 ``` ``` 0 ``` - 最初のトリボナッチ数は $ 0 $ です。 ``` 100000 ``` ``` 7927 ``` - $ a_n $ を $ 10007 $ で割った余りを出力することに気をつけてください。

N/A

N/A