fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int MOD = 1e9+7;
  5.  
  6. int calc(vector<int> &v , int k){
  7. int res = 1;
  8. for(auto &it : v){
  9. if(it == 0) res = (res * k) % MOD;
  10. }
  11. return res;
  12. }
  13.  
  14. signed main() {
  15. ios_base::sync_with_stdio(false);
  16. cin.tie(nullptr);
  17. int t;
  18. cin >> t;
  19. while(t--){
  20. int n, k;
  21. cin >> n >> k;
  22. vector<int> v(n);
  23. for(auto &it : v) cin >> it;
  24.  
  25. int i = 0, j = n-1;
  26. int ans = calc(v, k);
  27. vector<int> pal = v;
  28. bool isPal = true;
  29.  
  30. while(i < j){
  31. if(v[i] > 0 && v[j] > 0){
  32. if(v[i] != v[j]){
  33. isPal = false;
  34. break;
  35. }
  36. }
  37. else if(v[i] == 0 && v[j] == 0){
  38. // Do nothing
  39. }
  40. else{
  41. if(v[i] == 0){
  42. pal[i] = pal[j];
  43. }
  44. else{
  45. pal[j] = pal[i];
  46. }
  47. }
  48. i++; j--;
  49. }
  50.  
  51. int revs = 0;
  52. if(isPal){
  53. int curr = 1;
  54. for(auto &it : pal){
  55. if(it == 0) curr = (curr * k) % MOD;
  56. }
  57. revs = curr;
  58. }
  59.  
  60. int pals = 0;
  61. if(isPal){
  62. i = 0; j = n-1;
  63. int curr = 1;
  64. while(i <= j){
  65. if(pal[i] == 0 && pal[j] == 0){
  66. curr = (curr * k) % MOD;
  67. }
  68. i++; j--;
  69. }
  70. pals = curr;
  71. }
  72.  
  73. int totRev = (revs - pals + MOD) % MOD;
  74. totRev = (totRev * 500000004) % MOD;
  75.  
  76. cout << (ans - totRev + MOD) % MOD << endl;
  77. }
  78. }
  79.  
Success #stdin #stdout 0.01s 5296KB
stdin
Standard input is empty
stdout
531889287