#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v[n];
    int x, y, z;
    rep(i, m) {
        cin >> x >> y >> z;
        x--;
        v[x].emplace_back(y, z);
    };
    ll dp[n + 1][1 << n];
    fill(dp[0], dp[n + 1], 0);
    dp[0][0] = 1;
    rep(i, n) {
        for (int bit = 0; bit < 1 << n; bit++) {
            if (!dp[i][bit]) continue;
            rep(use, n) {
                if (bit >> use & 1) continue;
                int nxt = bit | 1 << use;
                bool ng = false;
                for (auto p : v[i]) {
                    int cnt = 0;
                    rep(k, p.first) {
                        cnt += (nxt >> k) & 1;
                    }
                    if (cnt > p.second) {
                        ng = true;
                        break;
                    }
                }
                if (ng) continue;
                dp[i + 1][nxt] += dp[i][bit];
            }
        }
    }
    cout << dp[n][(1 << n) - 1] << endl;
    return 0;
}
#include<bits/stdc++.h> 
using namespace std;

int main(){
  int N;
  cin>>N;
  string S,T;
  cin>>S>>T;
  int ans=0;
  vector<int>A,B;
  for(int i=0,cnt=0;i<N;i++){
    if(S[i]=='0')A.push_back(i);
    if(T[i]=='0')B.push_back(i);
  }
  if(A.size()!=B.size()){
    cout<<"-1\n";return 0;
  }
  for(int i=0;i<A.size();i++){
    ans+=(A[i]!=B[i]);
  }
  cout<<ans<<'\n';
}