# Kickstart 2020 Round B WA in Test set 2 | Problem C

Hi, I am unable to understand why I’m getting a WA for test-set 2. The idea I’ve implemented it to count how many times a symbol would contribute to the final answer. I think I’m making some mistake in doing modulo with 1e9 but not able to understand where. Can you help me figure this out?

Here’s my code:

``````    #include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define lli long long int
#define ulli unsigned long long int
#define for0(i,n) for(long long int i=0;i<(long long int)n;i++)
#define for1(i,n) for(long long int i=1;i<(long long int)n;i++)
#pragma GCC target ("sse4.2")
#include <algorithm>

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
int cl=1;
const ulli bound = 1000000000;
while(t--){
string s;
cin>>s;
ulli curr=1, latest=1;
stack<lli> st;
st.push(1);
lli ea=0, we=0, no=0, so=0;
for0(i,s.size()){
if(s[i]>='0' && s[i]<='9'){
lli x = s[i]-'0';
st.push(x);
curr*=x;
} else if(s[i]!=')'){
switch(s[i]){
case 'E': ea=(ea+(curr%bound));
break;
case 'W': we=(we+(curr%bound));
break;
case 'N': no=(no+(curr%bound));
break;
case 'S': so=(so+(curr%bound));
break;
}
} else {
if(!st.empty()){
curr/=st.top();
st.pop();
}
}
}
lli ver = (so-no);
lli hor = (ea-we);
cout<<"Case #"<<cl<<": ";
if(bound+hor+1<0){
cout<<bound-(abs(hor)%bound)+1<<" ";
} else
(hor<0) ? cout<<bound+hor+1<<" " : cout<<(hor%bound)+1<<" ";
if(bound+ver+1<0){
cout<<bound-(abs(ver)%bound)+1<<" ";
} else
(ver<0) ? cout<<bound+ver+1<<"\n" : cout<<(ver%bound)+1<<"\n";
++cl;
}
return 0;
}
``````

it is overflowing the size of long long int, curr could go to more tha 1e18

But I’ve used unsigned long long int for curr and adding curr%1e9

but when u r pushing it in stack curr can go off limit when the case is something like this
9(S9(S9(S9(S…))))

i did a similar mistake, my suggestion would be when you are multiplying then also use modulo
`curr*=x;` use
`curr=(curr * x) % bound`;

Thanks,
I changed to this but it still gives the same verdict.

I guess won’t that be the case if I’m pushing curr to the stack, I’m pushing just the number I read into the stack.

with your code variable curr can go upto 9^500 something and u can store it in ulli

i used the same approach but i saved the numbers as string

Ohh I think I got it. Thanks.
Can you share the part handled the overflow with a string?

`````` stack<char>st;
string cur = "1";
string n = "0", so = "0", e = "0", w = "0";
forr(i, len) {
if (s[i] == '(')
continue;
if (s[i] >= '2' && s[i] <= '9') {
cur = multiply(cur, s[i]);
//cur *= (s[i] - '0');

st.push(s[i]);
}
else if (s[i] == ')') {
cur = longDivision(cur, st.top() - '0');
st.pop();
}
else {
if ((s[i] == 'N'))
n = findSum(n, cur)   ;
if ((s[i] == 'E'))
e = findSum(e, cur)   ;
if ((s[i] == 'W'))
w = findSum(w, cur)   ;
if ((s[i] == 'S'))
so = findSum(so, cur)   ;
}
}
int w2, e2, n2, so2;
w2 = mod(w, MOD);
e2 = mod(e, MOD);
n2  = mod(n, MOD);
so2 = mod(so, MOD);``````