#include <iostream>
#include <string>
using namespace std;
int k;
long long pot(const long long & a, long long n)
{
if (n == 1)
return a;
if (n % 2)
{
long long s = pot(a, n - 1);
return (a * s) % k;
}
else
{
long long s = pot(a, n / 2);
return (s * s) % k;
}
}
int main()
{
std::ios_base::sync_with_stdio(0);
int n;
string str;
long long licznik = 0;
cin >> n >> k;
cin >> str;
for (int i = str.size() - 2; i > 0; --i) // inicjacja
if (str[i] == '1')
++licznik;
if (licznik)
cout << pot(2LL, licznik) << endl;
else
cout << 1 << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBrOwoKbG9uZyBsb25nIHBvdChjb25zdCBsb25nIGxvbmcgJiBhLCBsb25nIGxvbmcgbikKewoJaWYgKG4gPT0gMSkKCQlyZXR1cm4gYTsKCWlmIChuICUgMikKCXsKCQlsb25nIGxvbmcgcyA9IHBvdChhLCBuIC0gMSk7CgkJcmV0dXJuIChhICogcykgJSBrOwoJfQoJZWxzZQoJewoJCWxvbmcgbG9uZyBzID0gcG90KGEsIG4gLyAyKTsKCQlyZXR1cm4gKHMgKiBzKSAlIGs7Cgl9Cn0KCmludCBtYWluKCkKewoJc3RkOjppb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwoKCWludCBuOwoJc3RyaW5nIHN0cjsKCWxvbmcgbG9uZyBsaWN6bmlrID0gMDsKCgljaW4gPj4gbiA+PiBrOwoKCWNpbiA+PiBzdHI7CgoJZm9yIChpbnQgaSA9IHN0ci5zaXplKCkgLSAyOyBpID4gMDsgLS1pKSAvLyBpbmljamFjamEgCgkJaWYgKHN0cltpXSA9PSAnMScpCgkJCSsrbGljem5pazsKCglpZiAobGljem5paykKCQljb3V0IDw8IHBvdCgyTEwsIGxpY3puaWspIDw8IGVuZGw7CgllbHNlCgkJY291dCA8PCAxIDw8IGVuZGw7Cn0=