एल्गोरिदम और डेटा संरचनाएँ

फ़िबोनाची अनुक्रम का n-वाँ पद (mod m) की गणना

फ़िबोनाची अनुक्रम इस तरह परिभाषित होता है कि हर अगला पद पिछले दो पदों को जोड़कर बनता है, जबकि पहले दो पद 0 और 1 हैं:

आपको संख्या n दी गई है, और इसका n-वाँ फ़िबोनाची मान m से मॉड्यूलो करने पर प्राप्त करना है।

क्योंकि हमें केवल का परिणाम चाहिए, n का मान बहुत बड़ा हो सकता है।

इनपुट

इनपुट की एकमात्र पंक्ति में दो पूर्णांक n (0 ≤ n ≤ ) और m (1 ≤ m ≤ 50) दिए होते हैं।

आउटपुट

कार्यक्रम को का परिणाम प्रिंट करना चाहिए।

उदाहरण

Input

Output

0 5

0

1 5

1

6 5

3

व्याख्या

  1. fib(0) = 0 ⇒ 0 mod 5 = 0

  2. fib(1) = 1 ⇒ 1 mod 5 = 1

  3. fib(6) = 8 ⇒ 8 mod 5 = 3

Hint 1

क्योंकि हम फ़िबोनाची संख्याओं की गणना m से मॉड्यूलो लेकर कर रहे हैं, और अगली संख्या हमेशा पिछली दो पर निर्भर करती है, किसी बिंदु पर ये संख्याएँ दोहराने लगती हैं। आप m से मॉड्यूलो की कई मानों को प्रिंट करके देख सकते हैं और यह पैटर्न नोट कर सकते हैं कि वे कब से दोहराना शुरू करते हैं।

Hint 2

जैसा कि संख्याएँ एक बिंदु पर दोहराना शुरू कर देती हैं, आप सारे मान एक-एक करके निकालने के बजाय सीधे n-वाँ फ़िबोनाची नंबर ज्ञात कर सकते हैं।

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue