#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,L=10000000000;
string s,t;
int main(void){
    cin>>n>>s;
    for(int i=0;i<n;i++)t+="110";
    if(s=="1")cout<<L*2<<endl;
    else if(n%3==1 && t.substr(0,n)==s)cout<<L-((n-1)/3)<<endl;
    else if(n%3==2 && t.substr(0,n)==s)cout<<L-((n-2)/3)<<endl;
    else if(n%3==0 && t.substr(0,n)==s)cout<<L-((n-3)/3)<<endl;
    else if(n%3==0 && t.substr(1,n)==s)cout<<L-(n/3)<<endl;
    else if(n%3==1 && t.substr(1,n)==s)cout<<L-((n-1)/3)<<endl;
    else if(n%3==2 && t.substr(1,n)==s)cout<<L-((n-2)/3)<<endl;
    else if(n%3==2 && t.substr(2,n)==s)cout<<L-((n+1)/3)<<endl;
    else if(n%3==0 && t.substr(2,n)==s)cout<<L-(n/3)<<endl;
    else if(n%3==1 && t.substr(2,n)==s)cout<<L-((n-1)/3)<<endl;
    else cout<<0<<endl;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <array>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

template<int mod>
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      std::swap(a -= t * b, b);
      std::swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend std::ostream &operator<<(std::ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend std::istream &operator>>(std::istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  static int get_mod() { return mod; }
};

constexpr int mod = (int)1e9 + 7;
using mint = ModInt<mod>;
void solve()
{
  ll n, P; cin >> n >> P;
  if(P == 2)
  {
    if(n == 1)
    {
      cout << 1 << "\n";
    }
    else
    {
      cout << 0 << "\n";
    }
  }
  else
  {
    mint res = mint(P - 1) * mint(P - 2).pow(n - 1);
    cout << res << "\n";
  }
}
int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int kkt = 1;
  //cin >> kkt;
  while(kkt--)
    solve();
  return 0;
}