Expert.
Put your skills to the test.

Problem summary

A generalized Fibonacci sequence has given positive f1,f2 and fk=fk−1+fk−2. Find the second least significant digit of fn in base p, or 0 if its representation has one digit.

Constraints

2 ≤ p ≤ 16; n has at most 100 decimal digits; each initial value has at most 100 base-p digits.

Worked example

Official sample; other valid outputs may exist.

13 11
1B A

1

Solution analysis

1. Only fn modulo p² affects its last two base-p digits. Parse both initial values modulo p², regardless of their original size.
2. The Fibonacci matrix Q=[[1,1],[1,0]] satisfies that the second component of Q^(n−1)[f2,f1] is fn. Compute the exponent from its decimal digits: if the processed prefix gives Q^e, the next digit d changes it to (Q^e)^10 Q^d. Decrement n as a decimal string first.
3. For the sample fn in base 13 is 811. Its residue modulo 13² is 11 in base 13, and dividing that residue by 13 gives digit 1.

Why it works

Reduction modulo p² commutes with all additions and multiplications in the recurrence. The matrix identity follows by induction from one Fibonacci step. Decimal digit processing maintains the exact required matrix power modulo p², and its second component is fn modulo p². Integer division by p extracts precisely the requested digit.

Watch out. Read n as text, and parse f1,f2 in base p. Handle n=1 without converting its exponent to an integer.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
using namespace std;
int sequenceMod;
struct Matrix{
    int a[2][2]={{0,0},{0,0}};
};
Matrix multiply(const Matrix&x,const Matrix&y){
    Matrix z;
    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            for(int k=0;k<2;++k){
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%sequenceMod;
            }
        }
    }
    return z;
}
Matrix power(Matrix x,int exponent){
    Matrix result;
    result.a[0][0]=result.a[1][1]=1;
    while(exponent>0){
        if(exponent%2==1){
            result=multiply(result,x);
        }
        x=multiply(x,x);
        exponent/=2;
    }
    return result;
}
int parse(const string&s,int base){
    int value=0;
    for(char c:s){
        int digit=c<='9'?c-'0':c-'A'+10;
        value=(value*base+digit)%sequenceMod;
    }
    return value;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int p;
    string n,first,second;
    cin>>p>>n>>first>>second;
    sequenceMod=p*p;
    // Subtract one from the decimal exponent, keeping harmless leading zeroes.
    int index=static_cast<int>(n.size())-1;
    while(n[index]=='0'){
        n[index--]='9';
    }
    --n[index];
    Matrix q;
    q.a[0][0]=q.a[0][1]=q.a[1][0]=1;
    Matrix result;
    result.a[0][0]=result.a[1][1]=1;
    for(char digit:n){
        result=multiply(power(result,10),power(q,digit-'0'));
    }
    int residue=(result.a[1][0]*parse(second,p)+result.a[1][1]*parse(first,p))%sequenceMod;
    cout<<"0123456789ABCDEF"[residue/p]<<'\n';
}