Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const ll mod = ll(1e9) + 7;
  7.  
  8. int n;
  9. vector<vector<ll> > dp;
  10. vector<char> arr;
  11.  
  12. int main (int argc, char *argv[])
  13. {
  14.     scanf("%d", &n);
  15.     dp.resize(n);
  16.     for(int i = 0; i < n; ++i)
  17.     {
  18.         dp[i].resize(n, 0);
  19.     }
  20.     arr.resize(n);
  21.     scanf(" %c", &arr[0]);
  22.     dp[0][0] = 1;
  23.     for(int i = 1; i < n; ++i)
  24.     {
  25.         scanf(" %c", &arr[i]);
  26.         if(arr[i - 1] == 'f')
  27.         {
  28.             for(int j = 0; j < n - 1; ++j)
  29.             {
  30.                 dp[i][j + 1] = dp[i - 1][j];
  31.                 dp[i][j + 1] %= mod;
  32.             }
  33.         } else
  34.         {
  35.             ll sum = 0;
  36.             for(int j = n - 1; j >= 0; --j)
  37.             {
  38.                 sum += dp[i - 1][j];
  39.                 sum %= mod;
  40.                 dp[i][j] = sum;
  41.             }
  42.         }
  43.     }
  44.     ll sum = 0;
  45.     for(int i = 0; i < n; ++i)
  46.     {
  47.         sum += dp[n - 1][i];
  48.     }
  49.     printf("%lld", sum % mod);
  50.  
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement