Language: C++

#ifndef __INTMOD_H__0001__
#define __INTMOD_H__0001__

#include <vector>
#include <iostream>
#include <cassert>
#include <iostream>

/* Modulus must be less than 0x80000000, and not be 0. */
template <uint32_t Modulus>
class IntMod {
	typedef int32_t Int;
	typedef uint32_t UInt;
	typedef int64_t Long;
	typedef uint64_t ULong;

public:
	template <unsigned int Modulus_>
	friend bool operator==(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <unsigned int Modulus_>
	friend bool operator!=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <unsigned int Modulus_>
	friend bool operator<(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <unsigned int Modulus_>
	friend bool operator<=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <unsigned int Modulus_>
	friend bool operator>(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <unsigned int Modulus_>
	friend bool operator>=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);

private:
	UInt value_m;

public:
	IntMod() { value_m = 0; }
	IntMod(UInt value) { value_m = value % Modulus; }
	IntMod(ULong value) { value_m = value % Modulus; }
	IntMod(Int value) {
		Int tmp = value % (Int)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(Long value) {
		Int tmp = value % (Long)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(const IntMod& other) : value_m(other.value_m) {}
	IntMod& operator=(const IntMod& other) { value_m = other.value_m; return *this; }
	
	const IntMod& operator+() const { return *this; }
	IntMod operator-() const { return IntMod(Modulus - value_m); }
	IntMod& operator++() {
		++value_m;
		if (value_m == Modulus) value_m = 0;
		return *this;
	}
	IntMod& operator--() {
		if (value_m == 0) value_m = Modulus;
		--value_m;
		return *this;
	}
	IntMod operator++(int dummy) {
		IntMod tmp(*this);
		++(*this);
		return tmp;
	}
	IntMod operator--(int dummy) {
		IntMod tmp(*this);
		--(*this);
		return tmp;
	}
	IntMod& operator+=(const IntMod& right) {
		value_m += right.value_m;		// value_m < 0x80000000
		if (value_m >= Modulus) value_m -= Modulus;
		return *this;
	}
	IntMod& operator-=(const IntMod& right) {
		if (value_m < right.value_m) value_m += Modulus;
		value_m -= right.value_m;
		return *this;
	}
	IntMod& operator*=(const IntMod& right) {
		value_m = ((ULong)value_m * right.value_m) % Modulus;
		return *this;
	}	
	IntMod& operator/=(const IntMod& right) {
		(*this) *= (right.Inverse());
		return *this;
	}
	// for power
	IntMod operator[](unsigned int exp) const {
		return Pow(exp);
	}

	/* Modulus must be a prime. */
	IntMod Inverse() const { return (*this).Pow(Modulus - 2); }
	IntMod Pow(UInt exp) const {
		IntMod product = 1;
		IntMod factor(*this);
		while (exp > 0) {
			if (exp & 1) product *= factor;
			factor *= factor;
			exp >>= 1;
		}
		return product;
	}
	UInt Get_value() const {
		return value_m;
	}

	static IntMod Fact(UInt num) {
		static std::vector<IntMod> table(1, 1);
		if (table.size() > num) return table[num];

		int old_size = table.size();
		table.resize(num + 1);
		for (int i = old_size; i <= num; i++) {
			table[i] = table[i - 1] * i;
		}
		return table[num];
	}

	static IntMod Combi(UInt n, UInt r) {
		if (n < r) throw "okashii";
		return IntMod::Fact(n) / (IntMod::Fact(n - r) * IntMod::Fact(r));
	}

	static std::vector<IntMod> Inverse_list(int size) {
		assert(size < Modulus);
		std::vector<IntMod> ret_arr(size + 1);
		ret_arr[1] = 1;
		for (int i = 2; i <= size; ++i) {
			ret_arr[i] = ((ULong)(Modulus - Modulus / i) * ret_arr[Modulus % i].Get_value()) % Modulus;
		}
		return ret_arr;
	}
};

template <unsigned int Modulus>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, const IntMod<Modulus> right) {
	IntMod<Modulus> ret(left);
	ret += right;
	return ret;
}

template <unsigned int Modulus>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret -= right;
	return ret;
}

template <unsigned int Modulus>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret *= right;
	return ret;
}

template <unsigned int Modulus>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret /= right;
	return ret;
}


template <unsigned int Modulus>
bool operator==(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m == right.value_m; }
template <unsigned int Modulus>
bool operator!=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m != right.value_m; }
/* for set/map */
template <unsigned int Modulus>
bool operator<(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m < right.value_m; }
template <unsigned int Modulus>
bool operator<=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m <= right.value_m; }
template <unsigned int Modulus>
bool operator>(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m > right.value_m; }
template <unsigned int Modulus>
bool operator>=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m >= right.value_m; }

template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, Integer right) { return left + IntMod<Modulus>(right); }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator+(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) + right; }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, Integer right) { return left - IntMod<Modulus>(right); }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator-(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) - right; }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, Integer right) { return left * IntMod<Modulus>(right); }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator*(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) * right; }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, Integer right) { return left / IntMod<Modulus>(right); }
template <unsigned int Modulus, class Integer>
IntMod<Modulus> operator/(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) / right; }

template <unsigned int Modulus>
std::istream& operator<<(std::istream& ist, const IntMod<Modulus>& val) {
	uint64_t tmp;
	ist >> tmp;
	val = tmp;
	return ist;
}

template <unsigned int Modulus>
std::ostream& operator<<(std::ostream& ost, const IntMod<Modulus>& val) {
	ost << val.Get_value();
	return ost;
}

typedef IntMod<1000000007> MInt;

#if 1
MInt operator"" _m(unsigned long long num) { return MInt(num); }
#endif

#endif


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <list>
#include <bitset>

using namespace std;
#define REP(i,a,n) for(int i = (a); i < (int)(n); ++i)
#define REPM(i,n,a) for(int i = ((n) - 1); i >= (a); --i)
#define EPS 0.0001
#define INF 0x3FFFFFFF
#define INFLL 0x3FFFFFFF3FFFFFFF
#define INFD 1.0e+308
#define FLOAT setprecision(16)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;

template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(begin(dest), end(dest), val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
//sum, 累積和
// 負のときの割り算に注意
#if 1
#include <array>
#include <unordered_set>
#include <unordered_map>
template<class T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
#endif

struct CompBySecond {
	bool operator()(const PP& a, const PP& b) const {
		return a.second < b.second || (a.second == b.second && a.first < b.first);
	}
};

template<class T>
class Array {
	T* ptr_m;
	size_t size_m;
};

//#include "Union_Find.h"

int N, M;
string S;
vector<int> L, R;
int X[3000];
int W[3000];
int O[3000];
bool flg[3000];
MInt DP[3001][3001];

MInt C(int n, int r) 
	return MInt::Combi(n, r);
}

int main() {
	cin >> N >> M >> S;
	REP(i, 0, M) {
		int l, r;
		cin >> l >> r;
		--l;
		L.push_back(l);
		R.push_back(r);
	}
	REP(i, 1, L.size()) {
		if (R[i - 1] >= R[i]) {
			L.erase(L.begin() + i);
			R.erase(R.begin() + i);
			--i;
		}
	}
	REP(i, 1, L.size()) {
		if (R[i - 1] < L[i]) {
			L.insert(L.begin() + i, R[i - 1]);
			R.insert(R.begin() + i, R[i - 1] + 1);
		}
	}


	M = L.size();
	REP(i, 0, M) {
		X[i] = i == M - 1 ? R[M - 1] - L[M - 1] : L[i + 1] - L[i];
		W[i] = R[i] - L[i];
		O[i] = count(S.begin(), S.begin() + R[i], '1');
	}

	DP[0][count(S.begin(), S.begin() + L[0], '1')] = 1;
	REP(i, 1, M + 1) {
		REP(j, max(0, X[i - 1] + O[i - 1] - W[i - 1]), min(N, O[i - 1]) + 1) {
			REP(k, 0, min(j, X[i - 1]) + 1) {
				DP[i][j] += DP[i - 1][j - k] * C(X[i - 1], k);
			}
		}
	}
	cout << DP[M][O[M - 1]].Get_value() << endl;
	return 0;
}


Compiler output:
a.cc:10:11: error: 'uint32_t' has not been declared
   10 | template <uint32_t Modulus>
      |           ^~~~~~~~
a.cc:13:17: error: 'uint32_t' does not name a type
   13 |         typedef uint32_t UInt;
      |                 ^~~~~~~~
a.cc:7:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    6 | #include <cassert>
  +++ |+#include <cstdint>
    7 | #include <iostream>
a.cc:15:17: error: 'uint64_t' does not name a type
   15 |         typedef uint64_t ULong;
      |                 ^~~~~~~~
a.cc:15:17: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:19:21: error: 'bool operator==(const int&, const int&)' must have an argument of class or enumerated type
   19 |         friend bool operator==(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
      |                     ^~~~~~~~
a.cc:21:21: error: 'bool operator!=(const int&, const int&)' must have an argument of class or enumerated type
   21 |         friend bool operator!=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
      |                     ^~~~~~~~
a.cc:23:21: error: 'bool operator<(const int&, const int&)' must have an argument of class or enumerated type
   23 |         friend bool operator<(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
      |                     ^~~~~~~~
a.cc:25:21: error: 'bool operator<=(const int&, const int&)' must have an argument of class or enumerated type
   25 |         friend bool operator<=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
      |                     ^~~~~~~~
a.cc:27:21: error: 'bool operator>(const int&, const int&)' must have an argument of class or enumerated type
   27 |         friend bool operator>(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
      |                     ^~~~~~~~
a.cc:29:21: error: 'bool operator>=(const int&, const int&)' must have an argument of class or enumerated type
   29 |         friend bool operator>=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
      |                     ^~~~~~~~
a.cc:32:9: error: 'UInt' does not name a type; did you mean 'Int'?
   32 |         UInt value_m;
      |         ^~~~
      |         Int
a.cc:36:20: error: expected ')' before 'value'
   36 |         IntMod(UInt value) { value_m = value % Modulus; }
      |               ~    ^~~~~~
      |                    )
a.cc:37:21: error: expected ')' before 'value'
   37 |         IntMod(ULong value) { value_m = value % Modulus; }
      |               ~     ^~~~~~
      |                     )
a.cc:96:20: error: 'UInt' has not been declared
   96 |         IntMod Pow(UInt exp) const {
      |                    ^~~~
a.cc:106:9: error: 'UInt' does not name a type; did you mean 'Int'?
  106 |         UInt Get_value() const {
      |         ^~~~
      |         Int
a.cc:110:28: error: 'UInt' has not been declared
  110 |         static IntMod Fact(UInt num) {
      |                            ^~~~
a.cc:122:29: error: 'UInt' has not been declared
  122 |         static IntMod Combi(UInt n, UInt r) {
      |                             ^~~~
a.cc:122:37: error: 'UInt' has not been declared
  122 |         static IntMod Combi(UInt n, UInt r) {
      |                                     ^~~~
a.cc:139:17: error: 'int operator+(const int&, int)' must have an argument of class or enumerated type
  139 | IntMod<Modulus> operator+(const IntMod<Modulus>& left, const IntMod<Modulus> right) {
      |                 ^~~~~~~~
a.cc:146:17: error: 'int operator-(const int&, const int&)' must have an argument of class or enumerated type
  146 | IntMod<Modulus> operator-(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
      |                 ^~~~~~~~
a.cc:153:17: error: 'int operator*(const int&, const int&)' must have an argument of class or enumerated type
  153 | IntMod<Modulus> operator*(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
      |                 ^~~~~~~~
a.cc:160:17: error: 'int operator/(const int&, const int&)' must have an argument of class or enumerated type
  160 | IntMod<Modulus> operator/(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
      |                 ^~~~~~~~
a.cc:168:6: error: 'bool operator==(const int&, const int&)' must have an argument of class or enumerated type
  168 | bool operator==(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m == right.value_m; }
      |      ^~~~~~~~
a.cc:170:6: error: 'bool operator!=(const int&, const int&)' must have an argument of class or enumerated type
  170 | bool operator!=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m != right.value_m; }
      |      ^~~~~~~~
a.cc:173:6: error: 'bool operator<(const int&, const int&)' must have an argument of class or enumerated type
  173 | bool operator<(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m < right.value_m; }
      |      ^~~~~~~~
a.cc:175:6: error: 'bool operator<=(const int&, const int&)' must have an argument of class or enumerated type
  175 | bool operator<=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m <= right.value_m; }
      |      ^~~~~~~~
a.cc:177:6: error: 'bool operator>(const int&, const int&)' must have an argument of class or enumerated type
  177 | bool operator>(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m > right.value_m; }
      |      ^~~~~~~~
a.cc:179:6: error: 'bool operator>=(const int&, const int&)' must have an argument of class or enumerated type
  179 | bool operator>=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m >= right.value_m; }
      |      ^~~~~~~~
a.cc: In function 'std::istream& operator<<(std::istream&, const int&)':
a.cc:200:9: error: 'uint64_t' was not declared in this scope
  200 |         uint64_t tmp;
      |         ^~~~~~~~
a.cc:200:9: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:201:16: error: 'tmp' was not declared in this scope; did you mean 'tm'?
  201 |         ist >> tmp;
      |                ^~~
      |                tm
a.cc: In function 'std::ostream& operator<<(std::ostream&, const int&)':
a.cc:208:20: error: request for member 'Get_value' in 'val', which is of non-class type 'const int'
  208 |         ost << val.Get_value();
      |                    ^~~~~~~~~
a.cc: In function 'MInt C(int, int)':
a.cc:295:9: error: named return values are no longer supported
  295 |         return MInt::Combi(n, r);
      |         ^~~~~~
a.cc:337:33: error: request for member 'Get_value' in 'DP[M][O[(M - 1)]]', which is of non-class type 'MInt' {aka 'int'}
  337 |         cout << DP[M][O[M - 1]].Get_value() << endl;
      |                                 ^~~~~~~~~