output_description: Print the number of the ways to press the keys N times in total such that the
  editor displays the string s in the end, modulo 10^9+7.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      s
attempt: #include<bits/stdc++.h>
  #define range(i,a,b) for(int i = (a); i < (b); i++)
  #define rep(i,b) for(int i = 0; i < (b); i++)
  #define all(a) (a).begin(), (a).end()
  #define show(x)  cerr << #x << " = " << (x) << endl;
  //const int INF = 1e8;
  using namespace std;
  
  const long long M = 1000000007;
  
  //x^n mod M
  typedef long long ull;
  ull power(ull x, ull n){
  	ull res = 1;
  	if(n > 0){
  		res = power(x, n / 2);
  		if(n % 2 == 0) res = (res * res) % M;
  		else res = (((res * res) % M) * x ) %M;
  	}
  	return res;
  }
  
  int main(){
  	int n;
  	string s;
  	cin >> n >> s;
  
  	vector<long long> dp(n + 1, 0);
  	dp[0] = 1;
  	rep(i,n){
  		vector<long long> _dp(n + 1, 0);
  		rep(j,n + 1){
  			if(j == 0) (_dp[j] += dp[j]) %= M;
  			else (_dp[j - 1] += dp[j]) %= M;
  			(_dp[j + 1] += dp[j] * 2LL) %= M;
  		}
  		dp = _dp;
  		//for(auto j : dp){ for(auto k : j){ cout << k <<  ' '; } cout << endl; } cout << endl;
  	}
  	cout << dp[s.size()] * power(power(2,s.size()), M - 2) % M  << endl;
  }
  
problem_description: Statement
  
  Sig has built his own keyboard. Designed for ultimate simplicity, this
  keyboard only has 3 keys on it: the `0` key, the `1` key and the backspace
  key.
  
  To begin with, he is using a plain text editor with this keyboard. This editor
  always displays one string (possibly empty). Just after the editor is
  launched, this string is empty. When each key on the keyboard is pressed, the
  following changes occur to the string:
  
    * The `0` key: a letter `0` will be inserted to the right of the string.
    * The `1` key: a letter `1` will be inserted to the right of the string.
    * The backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is deleted.
  
  Sig has launched the editor, and pressed these keys N times in total. As a
  result, the editor displays a string s. Find the number of such ways to press
  the keys, modulo 10^9 + 7.
samples: [{"input": "3\n    0", "output": "5\n    \n\nWe will denote the backspace key by `B`. The following 5 ways to press the\nkeys will cause the editor to display the string `0` in the end: `00B`, `01B`,\n`0B0`, `1B0`, `BB0`. In the last way, nothing will happen when the backspace\nkey is pressed.\n\n* * *"}, {"input": "300\n    1100100", "output": "519054663\n    \n\n* * *"}, {"input": "5000\n    01000001011101000100001101101111011001000110010101110010000", "output": "500886057"}]