/* FILE: nPartition2Easy.cpp   last change: 27-Feb-2013   author: Romeo Rizzi
 * an exponential 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

// una semplice soluzione ricorsiva che prova tutti i 2^n sottoinsiemi di beni:
unsigned long long int numSol( int i, int target_p, int target_v) {
  // numero di scelte di beni ricompresi in (p[i], v[i]), (p[i+1], v[i+1]), ...,  (p[n-1], v[n-1]), con somma dei pesi = target_p e somma dei valori = target_v 
  if( i >= n ) return (int) ( ( target_p == 0 ) &&  ( target_v == 0 ) ); 
  return numSol( i+1, target_p, target_v) + numSol( i+1, target_p -p[i], target_v -v[i] );
} 

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;
  fout << numSol( 0, target_p, target_v) << endl;
  fout.close();
  return 0;
}