Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define Buildup() ios::sync_with_stdio(false),cin.tie(nullptr)
- #define make_unique(x) (x).resize(unique(all((x)))-(x).begin())
- #define rotate(x,k) rotate(x.begin(),x.begin()+k,x.end());
- #define all(x) (x).begin(),(x).end()
- #define allr(x) (x).rbegin(),(x).rend()
- #define ceil(x,y) (x+y-1)/(y)
- #define sz(x) (int)(x).size()
- #define PI 3.141592653589793238
- #define ld long double
- #define ull unsigned long long
- #define ll long long
- #define nl '\n'
- #define ff first
- #define ss second
- #define IM INT_MAX
- #define IN INT_MIN
- #define LM LLONG_MAX
- #define LN LLONG_MIN
- #define pb push_back
- #define pp pop_back
- #define ins insert
- #define lb lower_bound
- #define ub upper_bound
- #define Nl '\n'
- #define itn int
- // const int M = 998244353;
- const int M = 1e9+7;
- // const int N = 2e5+5;
- // const int N = 1e5+5;
- constexpr int inf = 1E9;
- #ifndef ONLINE_JUDGE
- #define dbg(x...) cerr << #x << " : ["; _print(x)
- #else
- #define dbg(x...)
- #endif
- void __print(int x) {cerr << x;}
- void __print(long x) {cerr << x;}
- void __print(ll x) {cerr << x;}
- void __print(ull x) {cerr << x;}
- void __print(ld x) {cerr << x;}
- void __print(float x) {cerr << x;}
- void __print(double x) {cerr << x;}
- void __print(char x) {cerr << '\'' << x << '\'';}
- void __print(const char *x) {cerr << '\"' << x << '\"';}
- void __print(const string &x) {cerr << '\"' << x << '\"';}
- void __print(bool x) {cerr << (x ? "T" : "F");}
- template<typename T, typename V>
- void __print(const pair<T, V> &x) {cerr << '{'; __print(x.ff); cerr << ','; __print(x.ss); cerr << '}';}
- template<typename T>
- void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
- void _print() {cerr << "]\n";}
- void __print(vector<bool> &v) {int f = 0; cerr << '{'; for (auto &&i : v) cerr << (f++ ? "," : "") << (i ? "T" : "F"); cerr << "}";}
- template <typename T, typename... V>
- void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
- template <size_t N> void __print(bitset<N> x) {cerr << x;}
- /* .....!! Start by doing what's necessary; then do what's possible;
- and suddenly you are doing impossible !!..... */
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("errorf.in", "w", stderr);
- #endif
- Buildup();
- int ___ = 1;
- // cin >> ___;
- while(___--){
- int n,m;
- cin>>n>>m;
- vector<int> v(n);
- for(auto &it : v) cin>>it;
- vector<int> dp(m+2);
- for(int i=0; i<n; i++){
- auto ndp = dp;
- for(int j=1; j<=m; j++){
- if(!i){
- if(!v[i]){
- ndp.assign(m+2,1);
- ndp.front() = ndp.back() = 0;
- }
- else ndp[v[i]] = 1;
- }
- else if(v[i]){
- ndp.assign(m+2,0);
- (ndp[v[i]] += dp[v[i]-1]) %= M;
- (ndp[v[i]] += dp[v[i]]) %= M;
- (ndp[v[i]] += dp[v[i]+1]) %= M;
- }
- else{
- (ndp[j] += dp[j-1]) %= M;
- (ndp[j] += dp[j]) %= M;
- (ndp[j] += dp[j+1]) %= M;
- }
- }
- dp = ndp;
- }
- for(int i=1; i<=m; i++) (dp[i] += dp[i-1]) %= M;
- cout<<dp[m]<<nl;
- // int ans = 0;
- // for(auto &x : dp) (ans += x) %= M;
- // dbg(dp);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment