#include <fstream>
#include <algorithm>
#include <cstring>

#define inf 100000000
#define ll long long
#define mod 1000000007
#define maxn 100001
#define vint vector<int>::iterator


using namespace std;

ifstream fin("melodii.in");
ofstream fout("melodii.out");

struct que
{
    long long n;
    int i;
}v[maxn];

int ans[maxn];

bool cmp (que a, que b)
{
    return a.n<b.n;
}

int t;
ll r;
ll u[2][2]={0,1,1,1};

void lgpow_matrix (ll m[][2], ll k)
{
    if (k==1)
    {
        memcpy (m,u,sizeof(u));
        return;
    }

    ll temp[2][2];
    memset (temp,0,sizeof(temp));

    lgpow_matrix (temp,k/2);

    for (int i=0; i<2; ++i)
      for (int j=0; j<2; ++j)
        for (int k=0; k<2; ++k)
        {
            m[i][j] = (m[i][j] + (temp[i][k]*temp[k][j])%r ) %r;
        }

    if (k%2)
    {
        ll temp = m[0][1];
        m[0][1] = (m[0][1] + m[0][0])%r;
        m[0][0] = temp;

        temp = m[1][1];
        m[1][1] = (m[1][1] + m[1][0])%r;
        m[1][0] = temp;
    }
}

int main()
{
    fin>>t>>r;

    for (int i=1; i<=t; ++i)
    {
        fin>>v[i].n;
        v[i].i = i;
    }

    sort (v+1,v+t+1,cmp);

    ll m[2];
    m[0] = 1; m[1] = 1;
    int current  = 1;

    for (int i=1; i<=t; ++i)
    {
        if (v[i].n==1)
        {
            ans[v[i].i] = 1;
            continue;
        }
        if (v[i].n==current)
        {
            ans[v[i].i] = ans[i-1];
            continue;
        }

        ll temp [2][2];
        memset (temp,0,sizeof(temp));
        lgpow_matrix (temp,v[i].n-current);

        ll wh = m[0];

        m[0] = (m[0]*temp[0][0]%r + m[1]*temp[0][1]%r)%r;
        m[1] = (wh*temp[1][0]%r + m[1]*temp[1][1]%r)%r;

        ans[v[i].i] = m[1];
         current = v[i].n;
    }

    for (int i=1; i<=t; ++i)
    {
        fout<<ans[i]<<"\n";
    }

}