URI Online Judge | 1968

The Undiscovered Country

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 2

Last October 12th we celebrated in Brazil the Children's Day. We adults should live more in children's world, for the opposite is not working, not at all. We adults have split the world into nations, and the children are those who suffer the most from the wars. We adults have built a wealth distribution system, and the children are those who suffer the most from hunger. But there is an Undiscovered Country, not so far from those who still preserve a little bit of imagination, that belongs to the children. There is no war there, or poverty, or hunger. There the children play day and night.

But a catastrophe is happening to the Undiscovered Country. A catastrophe! The sheep which used to live in the Undiscovered Country have ended up getting old, or sick, or swallowed by boa constrictors. This way, the baobabs have started to grow and spread over the entire country. Now, the citizens have to move urgently. In order to facilitate the evacuation, all the citizens have been numbered from A to B (it is obvious that this idea has come from the adults — they love these things!). In order to define who would be the leaders of the groups during the evacuation, someone has suggested that the leaders should be all those who have received a prime number (it is obvious that this idea has come from a child — children have a lot of imagination and they love pleasing themselves with things that need no further explanation!). But soon another idea came forth:

— A prime number is a number that has exactly 2 divisors. What if the leaders were those who have received a number with exactly N divisors?

All the children loved the idea. The adults, on the other hand, needed a long time to debate how the number N should be chosen. When finally the number N was chosen, each citizen who were not leader of a group should pick up the group he or she liked the most to enter it. No other restriction was imposed to the groups. Nothing was preventing, for example, a group of consisting only of its leader. Note that, depending on the value of N, there would not be any group at all.

Knowing the values of A, B and N, release the child inside you and try to figure out the total number of possibilities for the formation of the groups. If, for example, A = 5, B = 8 and N = 4, situation in which the leaders are the citizens 6 and 8, there are 4 possibilities:

Input

The single input line consists only of the positive integers A, B and N (AB; B, N ≤ 107).

Output

Output a line containing a single value which represents the number of possibilities for the formation of the groups. As this number can be very large, print only the remainder it leaves when divided by 109 + 7.

Input Samples Output Samples

5 8 4

4

1 10 2

4096

1 100 5

494092823