ფიბონაჩის მიმდევრობა განისაზღვრება შემდეგნაირად: მისი პირველი ორი წევრი 1-ის ტოლია, ხოლო ყოველი მომდევნო წევრი წინა ორი წევრის ჯამის ტოლია. თუ ფიბონაჩის მიმდევრობის წევრებს თანმიმდევრულად ჩავწერთ, მივიღებთ სტრინგს:

11235813213455...

გაარკვიეთ N-ური ციფრი ამ მიმდევრობაში.

შესატანი მონაცემები: ერთადერთ სტრიქონში ერთი მთელი რიცხვი N (1 ≤ N ≤ 10000000).

გამოსატანი მონაცემები: ერთადერთ სტრიქონში - საძებნი ციფრი.

მაგალითები

შესატანი მონაცემები
14
                  დაკოპირება

გამოსატანი მონაცემები
5
                  დაკოპირება