#include<cstdio>

 #include<cctype>

 using namespace std ; 

 struct state {

     int len ;

     int p ;

     int h ;

     int last ;

     state ( const int len , const int p , const int h ,

             const int last ) : len ( len ) , p ( p ) , h ( h ) ,

             last ( last ) {} ;

     int hash () const {

         return len *  +  * p + h *  + last ;

         //this is a perfect hash

     }

 } ;

 const int MAXN =  ;

 const long long MOD = ( long long ) ( 1e9 +  ) ;

 int N , M , K ;

 int G [ MAXN ] [ MAXN ] ;

 char s [ MAXN ] ; 

 const int size_of_dp =  ;

 long long dp [ size_of_dp ] ;

 bool vis [ size_of_dp ] ;

 int main () ; //complete checking checked

 long long D ( const state o ) ; //complete

 long long T ( const state o , const int p ) ;//complete

 long long T0 ( const state o , const int p ) ;//complete

 long long T1 ( const state o , const int p ) ;//complete

 long long T2 ( const state o , const int p ) ;//complete

 long long T3 ( const state o , const int p ) ;//complete

 long long T4 ( const state o , const int p ) ;//complete

 long long T5 ( const state o , const int p ) ;//complete

 long long D ( const state o ) {

     if ( vis [ o . hash () ] ) return dp [ o . hash () ] ;

     vis [ o . hash () ] = true ;

     if ( o . len == K ) {

         if ( o . h ==  && o . last <  )

             return dp [ o . hash () ] =  ;

         else return  ;

     }

     long long ans =  ;

     for ( int i =  ; i <= N ; ++ i )

     if ( G [ o . p ] [ i ] ) {

         ans += T ( o , i ) ;

         ans %= MOD ;

     }

     #ifdef DEBUG

     printf ( "(%d,%d,%d,%d)=%lld\n" , o . len , o . p , o . h , o . last , ans ) ;

     #endif

     return dp [ o . hash () ] = ans ;

 }

 long long T ( const state o , const int p ) {

     switch ( o . last ) {

         case  : return T0 ( o , p ) ;

         case  : return T1 ( o , p ) ;

         case  : return T2 ( o , p ) ;

         case  : return T3 ( o , p ) ;

         case  : return T4 ( o , p ) ;

         case  : return T5 ( o , p ) ;

     }

     return  ;

 }

 int main () {

     freopen ( "trace.in" , "r" , stdin ) ;

     freopen ( "trace.out" , "w" , stdout ) ;

     scanf ( "%d%d%d" , & N , & M , & K ) ;

     scanf ( "%s" , s +  ) ;

     while ( M -- ) {

         int a , b ;

         scanf ( "%d%d" , & a , & b ) ;

         G [ a ] [ b ] = G [ b ] [ a ] =  ;

     }

     for ( int i =  ; i <= N ; ++ i ) G [  ] [ i ] =  ;

     printf ( "%lld\n" , D ( state (  ,  ,  ,  ) ) ) ;

     return  ;

 }

 long long T0 ( const state o , const int p ) {

     if ( s [ p ] == ')' && o . h >  )

         return D ( state ( o . len +  , p , o . h -  ,  ) ) ;

     if ( s [ p ] == '+' || s [ p ] == '-' ||

          s [ p ] == '*' || s [ p ] == '/' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     return  ;

 }

 long long T1 ( const state o , const int p ) {

     if ( isdigit ( s [ p ] ) )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] == '+' || s [ p ] == '-' ||

          s [ p ] == '*' || s [ p ] == '/' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] == ')' && o . h >  )

         return D ( state ( o . len +  , p , o . h -  ,  ) ) ;

     return  ;

 }

 long long T2 ( const state o , const int p ) {

     if ( s [ p ] == '+' || s [ p ] == '-' ||

          s [ p ] == '*' || s [ p ] == '/' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] == ')' && o . h >  )

         return D ( state ( o . len +  , p , o . h -  ,  ) ) ;

     return  ;

 }

 long long T3 ( const state o , const int p ) {

     if ( s [ p ] == '(' )

         return D ( state ( o . len +  , p , o . h +  ,  ) ) ;

     if ( s [ p ] == '-' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] == '' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] >= '' && s [ p ] <= '' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     return  ;

 }

 long long T4 ( const state o , const int p ) {

     if ( s [ p ] == '' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] >= '' && s [ p ] <= '' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] == '(' )

         return D ( state ( o . len +  , p , o . h +  ,  ) ) ;

     return  ;

 }

 long long T5 ( const state o , const int p ) {

     if ( s [ p ] == '' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] >= '' && s [ p ] <= '' )

         return D ( state ( o . len +  , p , o . h ,  ) ) ;

     if ( s [ p ] == '(' )

         return D ( state ( o . len +  , p , o . h +  ,  ) ) ;

     return  ;

 }