## Angie and Functions

View as PDF

Points: 20 (partial)
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type

Angie is studying functions!

For her homework, she was asked to figure out the coefficients in the following function: (All the coefficients are integers)

To assist her on this question, her math teacher has allowed her to ask queries in the following form:

Given an integer , what is ?

However, as he doesn't want to give her too many hints, she can only make up to queries.

Angie has just started the year and isn't sure how to approach the problem. Can you help her solve it?

Not only will the answers to your queries be given modulo , your output should be modulo as well.

#### Constraints         #### Interaction Format

The first and only line of input will be the integer .

After that, you will begin interaction.

To make a query, output ? x where x is an integer that satisfies the constraints for given above ( ).

Then, you will receive an integer denoting the value of . If at any point you make an invalid query, exceed the maximum query count, or give an that is out of the limits you will receive instead. It's guaranteed that will never be for any valid .

Once you've completed the problem, output your answer in the form ! c_1 c_2 ... c_N c_N+1, where are the coefficients in . The interactor will give no further output at this point.

Important Notes/Reminders

• All input and output will be modulo . Be careful of how modulo works with negative numbers (i.e. )
• Always flush after writing to Standard Output
• If you ever receive as input, make sure to terminate the program (i.e. exit(0); in C++). Otherwise, you will receive TLE instead of WA

#### Sample Interaction

Note the following:

• The sample case here is where • >>> denotes your output. Do not actually print >>>
3
>>> ? 3
106
>>> ? 5
536
>>> ? 1000000004
999999831
>>> ! 5 1000000003 2 1

Note the following:

• The answers are outputted modulo .
• ? 1000000004 is the equivalent of asking for . and 