ციფრები ფიბონაჩის მიმდევრობაში

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


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

11235813213455...

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

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

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




მაგალითები

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