Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*--------------AUTHOR : LANGAOP----------- */
- #include<bits/stdc++.h>
- #include<iostream>
- #include<iomanip>
- #include<vector>
- #include<string>
- #include<math.h>
- #include<map>
- #include<algorithm>
- #include<set>
- #include<unordered_map>
- #include <unordered_set>
- #define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
- using namespace std;
- #define ff first
- #define ss second
- #define pb push_back
- #define int long long int
- typedef long double lld;
- #define FOR(i,n) for(int i=0;i<n;i++)
- #define yes cout<<"YES"<<endl;
- #define no cout<<"NO"<<endl;
- #define MOD 1000000007
- #define vi vector<int>
- #define pii pair<int, int>
- #define vii vector<pii>
- #define fr front()
- #define bk back()
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- typedef vector<char> vc;
- typedef vector<string> vs;
- typedef vector<pair<int, int> > vpii;
- typedef unordered_set<int> us;
- typedef map<int,int> mp;
- //debugging
- #ifndef ONLINE_JUDGE
- #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
- #else
- #define debug(x)
- #endif
- void _print(int t) {cerr << t;}
- void _print(string t) {cerr << t;}
- void _print(char t) {cerr << t;}
- void _print(lld t) {cerr << t;}
- void _print(double t) {cerr << t;}
- template <class T, class V> void _print(pair <T, V> p);
- template <class T> void _print(vector <T> v);
- template <class T> void _print(set <T> v);
- template <class T, class V> void _print(map <T, V> v);
- template <class T> void _print(multiset <T> v);
- template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
- template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
- template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
- template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
- template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
- template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
- //Constants
- const long double pi= 3.141592653589793238;
- const int INF= 1e18;
- const int mod=1e9+7;
- //MATHEMATICAL FUNCTIONS
- int gcd(int a, int b){if (b == 0)return a;return gcd(b, a % b);} //gcd
- int lcm(int a, int b){return (a/gcd(a,b)*b);} //lcm
- //sieve
- vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
- //binary exponentation
- int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
- //CHECK
- bool isprime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
- bool ispoweroftwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));}
- bool isperfectsquare(int x){if (x >= 0) {int sr = sqrt(x);return (sr * sr == x);}return false;}
- int ceils(int x, int y) {return x / y + (x % y > 0);}
- // Operator overloads
- template<typename T1, typename T2> // cin >> pair<T1, T2>
- istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
- template<typename T> // cin >> vector<T>
- istream& operator>>(istream &istream, vector<T> &v){for (auto &it : v)cin >> it;return istream;}
- template<typename T1, typename T2> // cout << pair<T1, T2>
- ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
- template<typename T> // cout << vector<T>
- ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
- //USEFUL
- void printarr(int arr[], int n){FOR(i,n) cout << arr[i] << " ";cout << "\n";}
- void solve(){
- int n,m;
- cin>>n>>m;
- vi v(n);
- cin>>v;
- vector<vector<int> > dp(m+1,vector<int> (n,0));
- for(int i=0;i<n;i++){
- if(i==0){
- if(v[i]!=0){
- dp[v[i]][i]=1;
- }
- else{
- for(int j=1;j<=m;j++){
- dp[j][i]=1;
- }
- }
- }
- else{
- if(v[i]!=0){
- dp[v[i]][i]+=(dp[v[i]][i-1]%mod+dp[v[i]-1][i-1]%mod)%mod;
- if(v[i]+1<=m){
- dp[v[i]][i]+=(dp[v[i]+1][i-1])%mod;
- }
- }
- else{
- for(int j=1;j<=m;j++){
- dp[j][i]=(dp[j-1][i-1]%mod+dp[j][i-1]%mod)%mod;
- if(j<m){
- dp[j][i]+=(dp[j+1][i-1]%mod)%mod;
- }
- dp[j][i]%=mod;
- }
- }
- }
- }
- debug(dp);
- if(v[n-1]!=0){
- cout<<dp[v[n-1]][v[n-1]];
- }
- else{
- int res=0;
- for(int j=1;j<=m;j++){
- debug(dp[j][n-1]);
- res=(res%mod+dp[j][n-1]%mod)%mod;
- // res=(res%mod+dp[j][n-1]%mod)%mod;
- debug(res);
- }
- debug(res);
- cout<<res<<endl;
- }
- }
- int32_t main()
- {
- fast;
- // #ifndef ONLINE_JUDGE
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // #endif
- int t;
- t=1;
- // cin>>t;
- while(t--){
- // cout<<t;
- solve();
- }
- return 0;
- }
Advertisement
RAW Paste Data
Copied
Advertisement