题解

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a=1,b=1,c=1,d=3;
    if(n==4)cout<<d;
    else if(n<4)cout<<1;
    else{
        n-=4;
        while(n--){
            a = b + c + d;
            b = c;
            c = d;
            d = a;
            a %= 10000;
            b %= 10000;
            c %= 10000;
            d %= 10000;
        }
    }
    cout <<  a ;
}