打飞机

Time Limit: 1s, Memory Limit: 128MB

背景

机房历2817年, 农民 (Famer Tao) 经过长期努力务农, 终于拥有了辽阔无边的农田, 被人们尊称为”农民之王”。
农民之王可不是那么好当, Famer Tao除了每天需要每天辛勤耕耘农田以外, 还要抵御蝗虫獾猪等物种的入侵。
这天, 何老师 (Miracle) 发现了这一片肥沃的农田, 于是派出大量轰炸机准备轰炸农民的领土, 让农民屈服割让农田。
“农民之王” Famer Tao可是那么好惹的! 处于众所周知的原因, 农民对打飞机特别敏感, 在这个领域有着深入的研究和高 潮 超的科技。
Miracle派出的战斗机被Famer Tao的”超级无敌全自动激光发生器”识别成了[latex][L, R][/latex]中的一个整数, 每个区间内整数都恰好对应一架飞机。激光器的运作方式非常独特, 它会随机在[latex][L, R][/latex]中不重复地选择[latex]K[/latex]个整数, 然后会发出一道激光击落这[latex]K[/latex]个整数最大公约数架飞机。
Famer发现Miracle竟然已经知道怎么预测激光器的期望击落数量, 于是他自然就想你求助了。

题目描述

给出Miracle战斗机编号左右端点[latex]L[/latex]和[latex]R[/latex], 以及激光武器的参数K, 问从区间[latex][L, R][/latex]内随机不重复地选择K个整数的期望最大公约数值。

输入格式

一行三个整数L, R, K, 整数之间以单个空格隔开

输出格式

你需要输出一个分数[latex]\frac{a}{b} \pmod{19260817}[/latex]作为 一个真正的粉丝的 答案, 你可以将其理解为[latex]a \times b^{-1} \pmod{19260817}[/latex]。

数据范围与约定

对于 100% 的数据, 有[latex]1 \le L \le R \le 10^6, 1 \le K \le R-L+1[/latex]