B - Si Stebbins System

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

問題文

無限に続く数列 AA があります.
A1=0,Ai+1=(Ai+3)mod13(i1)A_1 = 0, A_{i+1} = (A_i + 3) \bmod 13 \hspace{0.3em}\scriptsize (i \geq 1) と定めます.

AKA_K の値を求めてください.

ただし,非負整数 pp と 正整数 qq について pmodqp \bmod q は「ppqq で割ったあまり」を表します.

制約

  • 1K1091 \leq K \leq 10^9
  • KK は整数である

入力

入力は以下の形式で標準入力から与えられる.

KK

出力

答えを出力せよ.

サンプル

入力例1
3
出力例1
6

A1=0A2=(A1+3)mod13=(0+3)mod13=3A3=(A2+3)mod13=(3+3)mod13=6A_1 = 0 \\ A_2 = (A_1+3) \bmod 13 = (0+3) \bmod 13 = 3 \\ A_3=(A_2+3) \bmod 13 = (3+3) \bmod 13 = 6
が成り立ちます.


入力例2
7
出力例2
5

入力例3
2022
出力例3
5

Submit


Go (1.21)