Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <string.h>
- #include <queue>
- #include <math.h>
- #include <cmath>
- #include <map>
- #include <set>
- #include <vector>
- #include <algorithm>
- #include <bitset>
- #include <ctype.h>
- #include <cassert>
- #include <stack>
- #include <fstream>
- #include <unordered_map>
- #include <ctime>
- using namespace std;
- #define snd second
- #define fst first
- #define mp make_pair
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define pb push_back
- #define left _left
- #define right _right
- const ld pi = 3.14159265359;
- template < typename T > T abs(T x)
- {
- return x > 0 ? x : -x;
- }
- template < typename T > T sqr(T x)
- {
- return x * x;
- }
- const int maxn = 1000005;
- const ll mod = 1000000007;
- char s[maxn];
- int sp = 0;
- ll dp[205][205];
- int nxt()
- {
- while (s[sp] == ' ')
- {
- sp++;
- }
- if (s[sp] == '?')
- {
- sp++;
- return -1;
- }
- int res = 0;
- while (s[sp] != ' ')
- {
- res = res * 10 + s[sp] - '0';
- sp++;
- }
- return res;
- }
- ll fact[maxn], invFact[maxn];
- ll inv[maxn];
- ll C(ll n, ll k)
- {
- if (k > n)
- return 0;
- return (fact[n] * invFact[k] % mod) * invFact[n - k] % mod;
- }
- ll F(ll n, ll order)
- {
- n -= order - 1;
- if (n < 0)
- return 0;
- return (C(2 * n + order - 1, n) * inv[n + order] % mod) * order % mod;
- }
- ll get(ll currPos, ll prvPos, ll prvCoeff, ll prvOrder, ll order)
- {
- ll res = 0;
- for (int i = 0; i < 205; i++)
- {
- res += F(currPos - (prvPos - i), order) * dp[prvOrder][i] % mod;
- }
- return (res % mod) * prvCoeff % mod;
- }
- int main()
- {
- //gen();
- //freopen("a.in", "r", stdin);
- //srand(time(NULL));
- inv[0] = 1;
- inv[1] = 1;
- for (int i = 2; i < maxn; i++)
- {
- inv[i] = (mod - mod / i) * inv[mod % i] % mod;
- }
- fact[0] = invFact[0] = 1;
- for (int i = 1; i < maxn; i++)
- {
- fact[i] = (fact[i - 1] * i) % mod;
- invFact[i] = (invFact[i - 1] * inv[i]) % mod;
- }
- dp[1][0] = 1;
- dp[2][1] = 1;
- dp[2][0] = mod - 1;
- for (int i = 3; i < 205; i++)
- {
- for (int j = 0; j < 204; j++)
- dp[i][j + 1] = (mod + dp[i - 1][j] - dp[i - 2][j]) % mod;
- }
- int n;
- scanf("%d\n", &n);
- gets(s);
- s[strlen(s)] = ' ';
- if (nxt() > 0)
- {
- cout << 0 << endl;
- return 0;
- }
- if (n == 1)
- {
- cout << 1 << endl;
- return 0;
- }
- int g = nxt();
- if (g != -1 && g != 1)
- {
- cout << 0 << endl;
- return 0;
- }
- ll prvPos = 1, prvCoeff = 1, prvOrder = 1;
- for (int i = 2; i < n; i++)
- {
- int c = nxt();
- if (c == 0)
- {
- cout << 0 << endl;
- return 0;
- }
- if (c > 0)
- {
- ll res = get(i, prvPos, prvCoeff, prvOrder, c);
- prvPos = i;
- prvCoeff = res;
- prvOrder = c;
- }
- }
- cout << get(n, prvPos, prvCoeff, prvOrder, 1) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment