No.344 ある無理数の累乗

レベル : / 実行時間制限 : 1ケース 2秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 34
作問者 : FF256grhy

3

問題文

与えられた非負整数 $n$ に対して, $1 + \sqrt{3}$ の $n$ 乗の整数部分を $1000$ で割った余りの値, すなわち
\[ \left\lfloor \left( 1 + \sqrt{3} \, \right) ^ n \right\rfloor \bmod 1000 \] を計算してください.

入力

n

$n$ は整数で,
$0 \leq n \leq 10^9$
を満たす.

出力

値を出力し最後に改行してください.

サンプル

サンプル1
入力
0
出力
1

$ \left\lfloor \left( 1 + \sqrt{3} \, \right) ^ 0 \right\rfloor = \left\lfloor 1 \right\rfloor = 1 $

サンプル2
入力
2
出力
7

$ \left\lfloor \left( 1 + \sqrt{3} \, \right) ^ 2 \right\rfloor = \left\lfloor 7.464 \cdots \right\rfloor = 7 $

サンプル3
入力
12
出力
927

サンプル4
入力
123456789
出力
920

提出ページヘ