Language: C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef __int128 ll;
typedef long double ld;
const ll MOD = 1000000009;
const int INF = MOD + 1;
const ld EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator >(const Edge& e) const { return cost > e.cost; }
};

/*--------------------template--------------------*/
typedef ll Data;
typedef vector<Data> Array;
typedef vector<Array> Matrix;

bool is_zero(Data dat) { return (abs(dat) < EPS); }

Array modulo(Array ary)
{
	Array res = ary;
	REP(i, ary.size()) res[i] = ary[i] % MOD;
	return res;
}

Matrix modulo(Matrix mat)
{
	Matrix res = mat;
	REP(i, mat.size())REP(j, mat[0].size()) res[i][j] = mat[i][j] % MOD;
	return res;
}

Matrix operator*(const Matrix &lhs, const Matrix &rhs) 
{
	Matrix res(lhs.size(), Array(rhs[0].size(), 0));
	REP(i, lhs.size()) REP(j, rhs[0].size()) REP(k, rhs.size())
		res[i][j] = fma(lhs[i][k], rhs[k][j], res[i][j]);
	return modulo(res);
}

Array operator*(const Matrix &lhs, const Array &rhs) 
{
	Array res(lhs.size());
	REP(i, lhs.size())
		res[i] = inner_product(begin(lhs[i]), end(lhs[i]), begin(rhs), Data(0));
	return modulo(res);
}

Array operator*(Data scalar, const Array &rhs) 
{
	Array res(rhs.size());
	REP(i, rhs.size())
		res[i] = scalar * rhs[i];
	return modulo(res);
}

Matrix scalar(int size, Data k) {
	Matrix mat(size, Array(size, 0));
	REP(i, size) mat[i][i] = k;
	return modulo(mat);
}

Matrix operator^(const Matrix &lhs, const int n) {
	if (n == 0) return scalar(lhs.size(), 1);
	Matrix res = (modulo(lhs) * modulo(lhs)) ^ (n / 2);
	if (n % 2) res = modulo(res) * modulo(lhs);
	return modulo(res);
}


int main()
{
	ll w, h, n;
	for (int cs = 0; cin >> w >> h >> n&&w; cs++)
	{
		vector<pair<ll,ll>> v;
		REP(i, n)
		{
			ll x, y; cin >> x >> y;
			x--; y--;
			if (y == 0) continue;
			v.emplace_back(y, x);
		}
		n = v.size();
		sort(ALL(v));
		Array ary(w); ary[0] = 1;
		Matrix mat(w, Array(w));
		REP(i, w)REP(j, w)
		{
			if (abs(i - j) <= 1) mat[i][j] = 1;
		}
		ll tmp = 0, p = 0;
		while (1)
		{
			ll next;
			if (p < n) next = v[p].first;
			else next = h;
			ary = modulo(mat ^ (next - tmp - 1))*ary;
			if (next == h) break;
			vi obj; obj.push_back(v[p].second);
			p++;
			while (p < n && v[p].first == v[p-1].first)
			{
				obj.push_back(v[p].second);
				p++;
			}
			Array zero(w);
			Matrix objmat = mat;
			REP(i, obj.size()) objmat[obj[i]] = zero;
			ary = objmat*ary;
			tmp = next;
		}
		cout << "Case " << cs+1 << ": " << ary.back() << endl;
	}
	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:88:30: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'll' {aka '__int128'})
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                          ~~~ ^~ ~
      |                          |      |
      |                          |      ll {aka __int128}
      |                          std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127,
                 from a.cc:1:
/usr/include/c++/14/istream:170:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  170 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:170:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'bool&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:174:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  174 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:174:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'short int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:177:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  177 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:177:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:181:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  181 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:181:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:184:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:184:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'unsigned int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:188:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:188:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'long int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:192:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  192 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:192:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:199:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'long long int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:203:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  203 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:203:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:219:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  219 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:219:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'float&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:223:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  223 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:223:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'double&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:227:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  227 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:227:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: cannot bind non-const lvalue reference of type 'long double&' to a value of type 'll' {aka '__int128'}
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
/usr/include/c++/14/istream:328:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  328 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/14/istream:328:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: invalid conversion from 'll' {aka '__int128'} to 'void*' [-fpermissive]
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
      |                                 |
      |                                 ll {aka __int128}
a.cc:88:33: error: cannot bind rvalue '(void*)((long int)w)' to 'void*&'
/usr/include/c++/14/istream:122:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(__istream_type& (*)(__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  122 |       operator>>(__istream_type& (*__pf)(__istream_type&))
      |       ^~~~~~~~
/usr/include/c++/14/istream:122:7: note:   conversion of argument 1 would be ill-formed:
a.cc:88:33: error: invalid conversion from 'll' {aka '__int128'} to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'} [-fpermissive]
   88 |         for (int cs = 0; cin >> w >> h >> n&&w; cs++)
      |                                 ^
      |                                 |
      |                                 ll {aka __int128}
/usr/include/c++/14/i