Passing list (stack) in backtracing in python

I am trying to code this problem of hackerrank in python.

(if the link is not working, the problem is below)

"Goku has written a secret message using some blocks. Each block contains a character. Gohan likes to play with these blocks. He stacks these blocks on top of one another.

At any point of time, Gohan can move a block from the front of the secret message to the top of the stack or he can remove the block from the top and add it to the end of a new message that he has created.

Gohan creates this new message by adding the blocks that he removed from the top of the stack to the end of a new string in the order in which they were removed from the top of the stack.

The final message has the same number of characters as the original message i.e. all the blocks must be removed from the stack. Goku is worried that his original message might be lost.

He wants to know the number of ways in which Gohan could have recreated the original message and the number of distinct messages that Gohan could have created.

Sample Input: ball

Sample Output: 2 9 "

Gohan can create the following 9 messages : {llab, lalb, labl, allb, albl, abll, blla, blal, ball}

It is a backtracking problem in which we need to pass a stack in recursion and we are modify (insert/delete) stack in recursion. I am using normal list as stack.

The editorial of the problem is: (link)

(if the link is not working, the editorial is below)

Times_Recreated=0
Distinct_Messages=0

calculate_ans(OriginalMessage,Index,Stack st,NewMessage)

if Index = Length of the original message
        Pop the remaining characters in the stack and add them to NewMessage
        If NewMessage hasn't been encountered already, increment Distinct_Messages.
        If NewMessage is same as OriginalMessage, increment Times_Recreated.
        Return

Add OriginalMessage[Index] to the stack
Recurse for the remaining string  calculate_ans(OriginalMessage,Index+1,st,NewMessage)

Pop the character from the top of the stack to restore the original state

If the stack isn't empty
    Pop a character from the stack and add the character to NewMessage
    Recurse calculate_ans(OriginalMessage,Index,st,NewMessage)

I am trying below code but I could not pass list(stack) to recursion allowing its modification.

I think this list is global to the function. It is showing error- IndexError: pop from empty list

s= str(raw_input()) #string s as message input
words= set() # to store distinct messages Gohan can create
count=0 # number of ways in which Gohan could have recreated the original message

# s=message, i=index of s to be processed, stack= list as stack, new_s= new message 
def backtrack(s, i, stack, new_s):
    if i==len(s): 
        # pop the remaining characters from stack and add them to new_message 
        while stack:
            new_s=new_s+ stack.pop() 
        words.add(new_s) # insert new message to set words 
        if new_s==s:
            count+=1 # increase count if original message is obtained 
        return
    stack.append(s[i]) #push in stack 
    backtrack(s, i+1, stack, new_s) # backtrack 
    stack.pop() #pop from stack 
    if stack:
        new_s= new_s+stack.pop() # new message by appending stack pop 
        backtrack(s, i, stack, new_s) # backtrack 


# function call with i=0, a blank list stack and empty new message new_s
backtrack(s, 0, [], "") 
print count, len(words)  # printing output 

Please correct this code or provide some method/code to pass list in this situation.