oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

fibo Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

fibo.html

You are given a natural number N. Write a program that outputs the Nth Fibonacci number.

For those who were sleeping during lesson, the Fibonacci sequence is generated as follows:

f0 = 0
f1 = 1
fi = fi-1 + fi-2 for i ≥ 2

You are supposed to output an integer fN.

Input

On the first line is an integer N (1 ≤ N ≤ 2000) and another integer M (1 ≤ M ≤ 300000).

Output

On the first and only line output the integer fN mod M.
This is because fN might not fit into a integer or even long long.

Sample Input 1

3 10

Sample Output 1

2

Sample Input 2

1000 1000

Sample Output 2

875

Explanation for Sample Output 1

f2 = f1 + f0 = (1 + 0) % 10 = 1
f3 = f2 + f1 = (1 + 1) % 10 = 2

Explanation for Sample Output 2

f1000 = 43 466 557 686 937 456 435 688 527 675 040 625 802 564 660 517 371 780 402 481 729 089 536 555 417 949 051 890 403 879 840 079 255 169 295 922 593 080 322 634 775 209 689 623 239 873 322 471 161 642 996 440 906 533 187 938 298 969 649 928 516 003 704 476 137 795 166 849 228 875
f1000 mod 1000 = 875

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100401s32MBAverage
2021s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o fibo -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.