/* FILE: nPartition2.cpp   last change: 27-Feb-2013   author: Romeo Rizzi
 * the solver for problem nPartition2
 */

#define NDEBUG   // NDEBUG definita nella versione che consegno
#include <cassert>
#ifndef NDEBUG
#  include <iostream>  // uso di cin e cout non consentito in versione finale
#endif
#include <fstream>

using namespace std;

const int MAX_P = 10; const int MAX_V = 10; // peso e valore massimo di un bene
int n; const int MAX_N = 100; // numero di beni
int f; // numero di figli
int p[MAX_N], v[MAX_N]; // peso e valore di ciascun bene

// tabella di programmazione dinamica:
long double num[MAX_P*MAX_N/2 +1][MAX_V*MAX_N/2 +1];
/* SPIEGAZIONE:
   introdurremmo gli oggetti in scena uno per volta e,
   all'istante t, quando abbiamo a disposizione i primi t oggetti,
   
   num[i][j] = numero di sottoinsiemi dei primi t oggetti con somma dei pesi = i e somma dei valori = j. */
/* NOTA: anche se "long double" non garantisce di dedicare alla mantissa piu' bits di quanti non faccia un "long long int", e puo' pertanto risultare meno preciso di un "unsigned long long int", tuttavia in pratica si comporta tipicamente meglio in quanto fortunello negli arrotondamenti che si rivelano di fatto corretti quando il numero intero che vogliamo rappresentare termina con diversi 0. */ 

int main() {
  ifstream fin("input.txt"); assert( fin );
  fin >> n >> f; assert( n >= 0 ); assert( f >= 0 );
  int sum_p = 0, sum_v = 0; 
  for(int i = 0; i < n; i++) {
    fin >> p[i] >> v[i]; assert( p[i] >= 0 ); assert( v[i] >= 0 );
    sum_p += p[i], sum_v += v[i];
  }
  fin.close(); 
  ofstream fout("output.txt"); assert( fout );
  if( n == 0 ) { fout << 1 << endl; fout.close(); return 0; }
  if( f == 0 ) { fout << 0 << endl; fout.close(); return 0; }
  if( f == 1 ) { fout << 1 << endl; fout.close(); return 0; }
  assert( f == 2 );
  if( sum_p %2 ) { fout << 0 << endl; fout.close(); return 0; } 
  if( sum_v %2 ) { fout << 0 << endl; fout.close(); return 0; } 
  int target_p = sum_p /2; int target_v = sum_v /2;
  for(int i = 0; i <= target_p; i++)
    for(int j = 0; j <= target_v; j++)
       num[i][j] = 0;
  num[0][0] = 1;
  for(int t = 1; t <= n; t++) // introduciamo il bene t-esimo:
    for(int i = target_p; i-p[t] >= 0; i--)
      for(int j = target_v; j-v[t] >= 0; j--)
        num[i][j] += num[i-p[t]][j-v[t]];
  fout.precision(50); // 50 cifre decimali e' oltre 2^{100}
  fout << num[target_p][target_v] << endl;
  fout.close();
  return 0;
}