#include <bits/stdc++.h>

using namespace std;

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

char a[705][705],a2[705][705];
int margi[5001],margj[5001];

void Bordare(int n,int m){
    int i,j;
    for(i=0;i<=n+1;++i) a[i][0]=a[i][m+1]='A';
    for(j=0;j<=m+1;++j) a[0][j]=a[n+1][j]='A';
}

bool VerifCol(int n,int col){
    int i,k=0;
    for(i=1;i<=n;++i) if(a[i][col]=='N') ++k;
    if(k>1) return 1;
    return 0;
}

bool VerifLin(int lin,int m){
    int j,k=0;
    for(j=1;j<=m;++j) if(a[lin][j]=='N') ++k;
    if(k>1) return 1;
    return 0;
}

int main()
{
    int n,m,i,j,k,prov=0;
    fin>>n>>m;
    Bordare(n,m);
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            {fin>>a[i][j];a2[i][j]=a[i][j];}

    int ijos=0,jstanga=0,isus=0,jdreapta=0;
    for(j=1;j<=m && ijos==0;++j){
        for(i=n;i>=1;--i) if(a[i][j]=='N') {ijos=i;jstanga=j;break;}
    }
    for(j=m;j>=1 && isus==0;--j){
        for(i=1;i<=n;++i) if(a[i][j]=='N') {isus=i;jdreapta=j;break;}
    }
    if(a[ijos][jdreapta]=='A' && a[isus][jstanga]=='A') {fout<<0;return 0;}
    int jjos=0,istanga=0,jsus=0,idreapta=0;
    for(i=n;i>=1 && jjos==0;--i){
        for(j=n;j>=1;--j) if(a[i][j]=='N') {istanga=i;jjos=j;break;}
    }
    for(i=1;i<=n && jsus==0;++i){
        for(j=1;j<=n;++j) if(a[i][j]=='N') {idreapta=i;jsus=j;break;}
    }
    if(a[istanga][jsus]=='A' && a[idreapta][jjos]=='A') {fout<<0;return 0;}
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            if(a[i][j]=='N'){
                k=0;
                if(a[i-1][j]=='N') ++k;
                if(a[i+1][j]=='N') ++k;
                if(a[i][j-1]=='N') ++k;
                if(a[i][j+1]=='N') ++k;
                if(k==1){
                    if(a[i-1][j]=='N' || a[i+1][j]=='N'){
                        if(VerifLin(i,m)==1) {fout<<0;return 0;}
                        else{
                            a[i][j]='A';
                            if(a[i-1][j]=='N') {--i;--j;}
                        }
                    }
                    else if(a[i][j-1]=='N' || a[i][j+1]=='N'){
                        if(VerifCol(n,j)==1) {fout<<0;return 0;}
                        else{
                            a[i][j]='A';
                            if(a[i][j-1]=='N') {j-=2;}
                        }
                    }
                }
            }
        }
    }
    int x=1;
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j){
            if(a[i][j]=='N'){
                if(a[i-1][j]=='A' ||
                   a[i+1][j]=='A' ||
                   a[i][j-1]=='A' ||
                   a[i][j+1]=='A') {margi[x]=i;margj[x]=j;++x;}
            }
        }
    }
    for(i=1;i<x;++i){
        for(j=i+1;j<x;++j){
            if(a[margi[i]][margj[j]]=='A' && a[margi[j]][margj[i]]=='A') {fout<<0;return 0;}
        }
    }
    fout<<1;
    return 0;
}